Alberi binari

[shAke82]

Un albero binario di numeri interi si dice sinistro se, per ogni nodo dell'albero, la somma dei valori del sottoalbero sinistro e' maggiore della somma dei valori del sottoalbero destro (l'albero nullo puo' essere gestito come si vuole). Si scriva una funzione che verifichi se un albero binario e' sinistro oppure no.

:master:

ricorsivamente dovrebbero essere poche righe di codice, ma anche una "proposta" di soluzione e' ben accetta...

[Luc@s]

Originariamente inviato da shAke82
[saibal]
ricorsivamente dovrebbero essere poche righe di codice, ma anche una "proposta" di soluzione e' ben accetta... [/saibal]

2 domande:
1) cosa non ti viene?
2) in che lang?

[Luc@s]

cmq in C potrebbe essere na cosa simile:

/*
### Copyright (c) 2004 Luca Francesca
### This script is provided under the terms of the GNU General Public License
### (see http://www.gnu.org/licenses/gpl.html for the full license text.)
*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "Common.h"
#define YES 0
#define NO !YES

typedef struct _TreeNode *Node;

struct _TreeNode
{
	int data;
	Node l, r;
};

Node Init(int val);
Node Add(int val, Node aux);
void Delete(Node aux);
void ShowInOrder(Node aux);
uint IsRight(Node aux);

int main(int argc, char *argv[])
{
	srand(time(NULL));
	Node root = Init(1);
	int i = 0, ival = 0;
	for(i; i < 10;++i)
	{
		ival = i + (rand()%10);
		root = Add(ival, root);
	}
	if(IsRight(root) == YES)
	{
		puts("The tree is righted\n");
	}
	ShowInOrder(root);
	Delete(root);
	SAFE_DELETE(root)
  ExitFunction();
  return 0;
}

Node Init(int val)
{
	Node tmp;
	tmp = malloc(sizeof(struct _TreeNode));
	tmp->data = val;
	tmp->l = tmp->r = NULL;
	return tmp;
}
Node Add(int val, Node aux)
{
	if(aux == NULL)
	{
		aux = malloc(sizeof(struct _TreeNode));
		aux->data = val;
		aux->l = aux->r = NULL;
	}
	else if(val > aux->data)
		aux->l = Add(val, aux->l);
	else if(val <= aux->data)
		aux->r = Add(val, aux->r);
	return aux;
		
}

void ShowInOrder(Node aux)
{
     if (aux->l) ShowInOrder(aux->l);
     fprintf(stdout, "%d \n", aux->data);
     if (aux->r) ShowInOrder(aux->r);
}

uint IsRight(Node aux)
{
	uint nl, nr = 0;
	while(aux != NULL)
	{
		if(aux->l) nl++;
		if(aux->r) nr++;
	}
	return (nr > nl) ? YES : NO;
}

void Delete(Node aux)
{
	while(aux != NULL)
	{
		free(aux->l);
		free(aux->r);
		free(aux);
	}
	aux = NULL;
}

[shAke82]

Originariamente inviato da Luc@s
2 domande:
1) cosa non ti viene?
2) in che lang?

non preoccuparti di scrivermi il main, mi serve fare una funzione ricorsiva che ritorna 0 o 1...in pratica mi non riesco a capire l'algoritmo che devo usare... :master:

ora controllo la tua soluzione grazie

[Luc@s]

Originariamente inviato da shAke82
non preoccuparti di scrivermi il main, mi serve fare una funzione ricorsiva che ritorna 0 o 1...in pratica mi non riesco a capire l'algoritmo che devo usare... :master:

ora controllo la tua soluzione grazie

il listato lo ho buttato giu in 2 minuti.
PEr l'albero ti assicuro che va.........per la funz prova a vedere

[anx721]

Supponiamo di aver definito il tipo Tree come una struct che ha un campo intero el che rappresenta l'intero associato al nodo, e due campi puntatori a Tree, left e right che rappresentano rispettivamente il figlio sinistro e il figlio destro. Per realizzare la tua funzione, dapprima scriviamo una funzione ricorsiva che calcola la somma degli elementi di un albero:

int sum(Tree * tree){
     if(tree == NULL)
          return 0;
     return tree -> el + sum(tree -> left) + sum(tree -> right);
}

La funzione isLeaf ritorna 1 se l'albero è una foglia:

int isLeaf(Tree * tree){
     return (tree -> left == NULL) && (tree -> right == NULL);
}

A questo punto possiamo scrivere la tua funzione isLeft, che ritorna 1 se e solo se l'albero passato come argomento è sinistro; se l'albero è una foglia ritorna 0, se è NULL ritorna 1:

int isLeft(Tree *tree){
     //Sull'albero nullo ritorno 1
     if(tree == NULL)
          return 1;
     //Su una foglia ritorno 0
     if(isLeaf(tree))
          return 0;
     //controllo la proprietà sul sottoalbero sinistro
     //se non è una foglia
     if(! isLeaf(tree -> left))
          if(! isLeft(tree -> left))
               return 0;
     //controllo la proprietà sul sottoalbero destro
     //se non è una foglia
     if(! isLeaf(tree -> right))
          if(! isLeft(tree -> right))
               return 0;
     //infine controllo se la somma del sottoalbero
     //sinistro è maggiore della somma del sottoalbero destro
     if(sum(tree -> left) <= sum(tree -> right))
          return 0;
     return 1; 
}