Esercizio su alberi binari triangolari

[diegoves]

Salve a tutti! Ho appena fatto un compitino di dati e algoritmi, con questo esercizio all'interno:
"Scrivere una funzione ricorsiva che, passato come parametro un albero binario T, verifichi se è triangolare. Usare solo variabili locali d'appoggio, no array o altre strutture. Non si può modificare l'albero. L'interfaccia albero binario ha come metodi: root(), isEmpty(), hasLeft(), left(), hasRight(), right()" (quindi niente riguardante l'altezza dell'albero, il numero di nodi ecc ecc).
Come fare?
Cercando un po' su internet non ho trovato una effettiva definizione di albero triangolare, ma comunque è semplice: è un albero binario con tutti i livelli completi, quindi i suoi nodi sono in numero una potenza di 2 meno 1, e l'ultimo livello L dell'albero contiene 2^L nodi esterni.

http://farm9.staticflickr.com/8342/8220148475_512a7e407d_m.jpg

Essendo ricorsiva ho pensato di visitare l'albero, e conteggiare un "+1" se la ricorsione scende a sinistra, e "-1" se scende a destra, se finita la ricorsione il conteggio è a 0 allora risulta triangolare, cioè in questa maniera:

http://farm9.staticflickr.com/8483/8220148511_3843e41b86_m.jpg

ma sfortunatamente non basta, perché in questo caso verifica semplicemente se i nodi aventi figli ne hanno esattamente 2...!! Ovvero così:

http://farm9.staticflickr.com/8489/8221229302_0ef1296e70_m.jpg

Qualche consiglio su come farlo?

[diegoves]

Nessuno sa darmi una mano?

[__ZERO_UNO__]

def triangle_h(T, d)
if empty?(T) return 0;
if (has_children?(T)) d += 1
return 1 + triangle_h(left(T)) + triangle_h(right(T))
end

def triangle?(T, d)
return triangle_h(T, d) == pow(2, d + 1) - 1
end


depth = 0
verdict = triangle?(T, depth)

if (verdict)
print("It's a fantastic triangle tree!");
else
print("It's a common tree :(");


Forse funziona. :D
La funzione restituisce il numero di nodi e calcola la massima profondità(il numero di archi dalla radice ad una foglia).

[Vincenzo1968]

Edit

[Vincenzo1968]

La mia soluzione:


int isTriangular(Tree *head)
{
int leftHeight = -1;
int rightHeight = -1;

if( !head )
return 0;

if( !head->left && !head->right )
return 1;

if( !head->left || !head->right )
return -1;

leftHeight = isTriangular(head->left);
rightHeight = isTriangular(head->right);

if( leftHeight < 0 || rightHeight < 0 || leftHeight != rightHeight )
return -1;

return leftHeight + 1;
}


La funzione restituisce -1 se l'albero non è triangolare; altrimenti restituisce l'altezza.

Questo è il programma di prova:


#include <stdio.h>
#include <malloc.h>

#define MAX_STACK 512

//int MemoriaAllocata = 0;
//int MemoriaDeallocata = 0;

typedef struct tagTree
{
int data;
struct tagTree *left;
struct tagTree *right;
} Tree;

Tree *NewNode(int info);
void FreeTree(Tree *head);

int IsTriangular(Tree *head);

Tree *NewNode(int info)
{
Tree *r;

r = (Tree *) malloc(sizeof(Tree));

if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}

//MemoriaAllocata += sizeof(Tree);

r->data = info;
r->left = NULL;
r->right = NULL;

return r;
}

void FreeTree(Tree *head)
{
Tree *temp1, *temp2;

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( head == NULL )
return;

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;

while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2);
//MemoriaDeallocata += sizeof(Tree);
if ( top == 0 )
return;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
}
}

int isTriangular(Tree *head)
{
int leftHeight = -1;
int rightHeight = -1;

if( !head )
return 0;

if( !head->left && !head->right )
return 1;

if( !head->left || !head->right )
return -1;

leftHeight = isTriangular(head->left);
rightHeight = isTriangular(head->right);

if( leftHeight < 0 || rightHeight < 0 || leftHeight != rightHeight )
return -1;

return leftHeight + 1;
}

int main()
{
Tree *pTree1 = NULL;
Tree *pTree2 = NULL;

pTree1 = NewNode(1);
pTree1->left = NewNode(2);
pTree1->right = NewNode(3);
pTree1->left->left = NewNode(4);
pTree1->left->right = NewNode(5);
pTree1->right->left = NewNode(6);
pTree1->right->right = NewNode(7);
pTree1->left->left->left = NewNode(8);
pTree1->left->left->right = NewNode(9);
pTree1->left->right->left = NewNode(10);
pTree1->left->right->right = NewNode(11);
pTree1->right->left->left = NewNode(12);
pTree1->right->left->right = NewNode(13);
pTree1->right->right->left = NewNode(14);
pTree1->right->right->right = NewNode(15);


pTree2 = NewNode(1);
pTree2->left = NewNode(2);
pTree2->right = NewNode(3);
pTree2->left->left = NewNode(4);
pTree2->left->right = NewNode(5);
pTree2->right->left = NewNode(6);
pTree2->right->right = NewNode(7);
pTree2->left->left->left = NewNode(8);
pTree2->left->left->right = NewNode(9);
pTree2->left->right->left = NewNode(10);
pTree2->left->right->right = NewNode(11);


if ( isTriangular(pTree1) != -1 )
printf("\nL'albero 1 e' triangolare.\n");
else
printf("\nL'albero 1 non e' triangolare\n");

if ( isTriangular(pTree2) != -1 )
printf("\nL'albero 2 e' triangolare.\n");
else
printf("\nL'albero 2 non e' triangolare\n");

FreeTree(pTree1);
FreeTree(pTree2);

//printf("\nMemoria allocata : %d\nMemoria deallocata : %d\n\n", MemoriaAllocata, MemoriaDeallocata);

return 0;
}