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.



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:



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



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.
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;
}