[C] Costruire albero red-black

[strasy]

Salve a tutti,
sto studiando gli alberi red-black. Sulla teoria ci sono, ma nell'implementazione dei codici in linguaggio C mi sto un pò incartando.

Ho il codice per trovare la b-altezza di un albero. Ma prima devo avere il mio albero costruito con tutte le chiavi e colori al posto giusto. Come faccio a costruirlo? Cioè, se io ho un esempio di albero red-black, come posso costruire questo albero in linguaggio C?

Grazie!!

[WarDuck]

Devi procedere per passi.

Innanzitutto come rappresenti un albero vuoto.

Dopodiché come rappresenti un albero con un solo nodo, e di che colore è (la radice se non sbaglio deve essere di un determinato colore).

Ti consiglio di partire proprio dall'insert.

[strasy]

Allora, mi creo il nuovo tipo di dato per il colore del nodo:

typedef
enum {rosso,nero} tipo_colore;

poi mi creo la struttua per rappresentare un nodo:

typedef
struct nodo_rb
{
long chiave;
tipo_colore color;
struct nodo_rb *padre, *sinix, *dex;
}
tipo_nodorb;

e poi mi creo la struttua per rappresentare un albero:

typedef
struct albero_rb
{
tipo_nodorb *radice;
tipo_nodorb *nil;
}
tipo_alberorb;

adesso come faccio a costruire l'albero? ogni volta che inserisco un valore devo prestare attenzione a dove va inserito, al colore e a tutti i collegamenti (padre,sinistro e destro).
da dove devo iniziare?

ad esempio, se faccio:
int main()
{
int k;

printf("Inserisci la chiave di un nodo ");
scanf("%d", &k);
}

come faccio adesso a inserire il valore di k nella radice?e se poi faccio un ciclo, come faccio ogni volta che inserisco un nuovo valore a metterlo al posto giusto con tutti i collegamenti?

Ah, la radice deve essere di colore nero.

[strasy]

Sono riuscita a crearmi dei nodi e collegarli tra loro...ora devo assegnare al mio albero il primo nodo, così il mio albero viene riconosciuto dal puntatore al nodo radice (primo nodo)...solo che nn riesco ad effettuare questa assegnazione e non ne capisco il motivo. Riporto qui di seguito il mio codice:



#include <stdio.h>
#include <stdlib.h>

typedef
enum {rosso,nero} tipo_colore;

typedef
struct nodo_rb
{
int chiave;
tipo_colore color;
struct nodo_rb *padre, *sinix, *dex;
}
tipo_nodorb;

typedef
struct albero_rb
{
tipo_nodorb *radice;
tipo_nodorb *nil;
}
tipo_alberorb;

tipo_nodorb* crea_nodo(int val, tipo_colore col)
{
tipo_nodorb *punt;
punt = (tipo_nodorb *)malloc(sizeof(tipo_nodorb));
punt->chiave = val;
punt->color = col;
punt->padre = NULL;
punt->sinix = NULL;
punt->dex = NULL;
return punt;
}

tipo_nodorb* settings(tipo_nodorb *nodo, tipo_nodorb *sx, tipo_nodorb *dx, tipo_nodorb *px)
{
nodo->padre = px;
nodo->sinix = sx;
nodo->dex = dx;
return nodo;
}

int main()
{
tipo_nodorb *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9;

p1 = crea_nodo(21,nero);
p2 = crea_nodo(2,rosso);
p3 = crea_nodo(55,nero);
p4 = crea_nodo(1,nero);
p5 = crea_nodo(8,nero);
p6 = crea_nodo(34,rosso);
p7 = crea_nodo(89,rosso);
p8 = crea_nodo(5,rosso);
p9 = crea_nodo(13,rosso);

settings(p1,p2,p3,NULL);
settings(p2,p4,p5,p1);
settings(p3,p6,p7,p1);
settings(p4,NULL,NULL,p2);
settings(p5,p8,p9,p2);
settings(p6,NULL,NULL,p3);
settings(p7,NULL,NULL,p3);
settings(p8,NULL,NULL,p5);
settings(p9,NULL,NULL,p5);

printf("%d\t%d\t%d\t%d\t%d\n", p1->chiave, p1->color, p1->padre, p1->sinix->chiave, p1->dex->chiave);
printf("%d\t%d\t%d\t%d\t%d\n", p2->chiave, p2->color, p2->padre->chiave, p2->sinix->chiave, p2->dex->chiave);
printf("%d\t%d\t%d\t%d\t%d\n", p3->chiave, p3->color, p3->padre->chiave, p3->sinix->chiave, p3->dex->chiave);
printf("%d\t%d\t%d\t%d\t%d\n", p4->chiave, p4->color, p4->padre->chiave, p4->sinix, p4->dex);
printf("%d\t%d\t%d\t%d\t%d\n", p5->chiave, p5->color, p5->padre->chiave, p5->sinix->chiave, p5->dex->chiave);
printf("%d\t%d\t%d\t%d\t%d\n", p6->chiave, p6->color, p6->padre->chiave, p6->sinix, p6->dex);
printf("%d\t%d\t%d\t%d\t%d\n", p7->chiave, p7->color, p7->padre->chiave, p7->sinix, p7->dex);
printf("%d\t%d\t%d\t%d\t%d\n", p8->chiave, p8->color, p8->padre->chiave, p8->sinix, p8->dex);
printf("%d\t%d\t%d\t%d\t%d\n", p9->chiave, p9->color, p9->padre->chiave, p9->sinix, p9->dex);

return 0;
}



Ora se mi dichiaro

tipo_alberorb *b;

e poi assegno

b->radice = p1;

il programma non mi funziona più...perchè?

[strasy]

Ho risolto.
Al posto dell'operatore freccia (->) dovevo mettere l'operatore punto (.).

[Vincenzo1968]

Questa è l'implementazione dell'algoritmo descritto nel Cormen:

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

#define MAX_STACK 100

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

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

Tree *pNil = NULL;

Tree *NewNode(int info);
Tree *InsertNode(Tree *node, int key);
void InsertFixup(Tree **head, Tree **z);
Tree *DeleteNode(Tree *root, Tree *z);
void DeleteFixup(Tree **head, Tree **x);
void FreeTree(Tree *head);

void InitNil(Tree **p);

Tree *TreeRotateLeft(Tree *head, Tree *node);
Tree *TreeRotateRight(Tree *head, Tree *node);
void TreeSuccessor(Tree *current, Tree **result);
void TreePredecessor(Tree *current, Tree **result);

void ReverseInOrder(Tree *head);
void InOrder(Tree *head);
void PreOrder(Tree *head);
void PostOrder(Tree *head);

void SearchFirst(Tree *head, Tree **result, int key);
void SearchNext(Tree *head, Tree **result, int key);
void TreeMinimum(Tree *head, Tree **result);
void TreeMaximum(Tree *head, Tree **result);

int TreeSize(Tree *head);
int TreeDepth(Tree *head);

void InitNil(Tree **p)
{
	*p = NewNode(0);
	if ( *p )
	{
		(*p)->data = 0;
		(*p)->color = 'b';
		(*p)->left = NULL;
		(*p)->right = NULL;
		(*p)->father = NULL;
	}
	else
	{
		printf("Errore nell'inizializzazione di pNil.\n");
	}
}

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

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

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

	//MemoriaAllocata += sizeof(Tree);

	r->data = info;
	r->color = 'b'; // 'b' = Black; 'r' = Red
	r->father = pNil;
	r->left = pNil;
	r->right = pNil;

	return r;
}

Tree *InsertNode(Tree *node, int key)
{
	Tree *z = pNil;
	Tree *y = pNil;
	Tree *pRadice = pNil;

	z = NewNode(key);
	if ( z == pNil )
		return pNil;

	pRadice = node;

	while ( pRadice != pNil )
	{
		y = pRadice;
		if ( z->data < pRadice->data )
			pRadice = pRadice->left;
		else
			pRadice = pRadice->right;
	}

	z->father = y;
	if ( y == pNil )
	{
		printf("Inserisco la radice -> %d\n", key);

		node = z;
	}
	else
	{
		if ( z->data < y->data )
		{
			printf("Inserisco %d a sinistra di %d\n", z->data, y->data);

			y->left = z;
		}
		else
		{
			printf("Inserisco %d a destra di %d\n", z->data, y->data);

			y->right = z;
		}
	}

	z->left = pNil;
	z->right = pNil;
	z->color = 'r'; // Red

	InsertFixup(&node, &z);

	return node;
}

void InsertFixup(Tree **head, Tree **z)
{
	Tree *y = pNil;

	while ( (*z)->father->color == 'r' )
	{
		if ( (*z)->father == (*z)->father->father->left )
		{
			y = (*z)->father->father->right;
			if ( y->color == 'r' )
			{
				(*z)->father->color = 'b';
				y->color = 'b';
				(*z)->father->father->color = 'r';
				*z = (*z)->father->father;
			}
			else 
			{
				if ( *z == (*z)->father->right )
				{
					*z = (*z)->father;
					*head = TreeRotateLeft(*head, *z);
				}
				(*z)->father->color = 'b';
				(*z)->father->father->color = 'r';
				*head = TreeRotateRight(*head, (*z)->father->father);
			}
		}
		else
		{
			y = (*z)->father->father->left;
			if ( y->color == 'r' )
			{
				(*z)->father->color = 'b';
				y->color = 'b';
				(*z)->father->father->color = 'r';
				*z = (*z)->father->father;
			}
			else 
			{
				if ( *z == (*z)->father->left )
				{
					*z = (*z)->father;
					*head = TreeRotateRight(*head, *z);
				}
				(*z)->father->color = 'b';
				(*z)->father->father->color = 'r';
				*head = TreeRotateLeft(*head, (*z)->father->father);
			}
		}
	}

	(*head)->color = 'b';
}

Tree *DeleteNode(Tree *root, Tree *z)
{
	Tree *y = pNil;
	Tree *x = pNil;

	if ( root == pNil || z == pNil )
		return root;

	if ( z->left == pNil || z->right == pNil )
		y = z;
	else
		TreeSuccessor(z, &y);

	if ( y->left != pNil )
		x = y->left;
	else
		x = y->right;

	x->father = y->father;

	if ( y->father == pNil )
	{
		root = x;
	}
	else
	{
		if ( y == y->father->left )
			y->father->left = x;
		else
			y->father->right = x;
	}

	if ( y != z )
		z->data = y->data;

	if ( y->color == 'b' )
		DeleteFixup(&root, &x);

	free(y);
	//MemoriaDeallocata += sizeof(Tree);

	return root;
}

void DeleteFixup(Tree **head, Tree **x)
{
	Tree *w = pNil;

	while ( *x != *head && (*x)->color == 'b' )
	{
		if ( *x == (*x)->father->left )
		{
			w = (*x)->father->right;
			if ( w->color == 'r' )
			{
				w->color = 'b';
				(*x)->father->color = 'r';
				*head = TreeRotateLeft(*head, (*x)->father);
				w = (*x)->father->right;
			}

			if ( w->left->color == 'b' && w->right->color == 'b' )
			{
				w->color = 'r';
				(*x) = (*x)->father;
			}
			else
			{
				if ( w->right->color == 'b' )
				{
					w->left->color = 'b';
					w->color = 'r';
					*head = TreeRotateRight(*head, w);
					w = (*x)->father->right;
				}

				w->color = (*x)->father->color;
				(*x)->father->color = 'b';
				w->right->color = 'b';
				*head = TreeRotateLeft(*head, (*x)->father);
				*x = *head;
			}
		}
		else
		{
			w = (*x)->father->left;
			if ( w->color == 'r' )
			{
				w->color = 'b';
				(*x)->father->color = 'r';
				*head = TreeRotateRight(*head, (*x)->father);
				w = (*x)->father->left;
			}

			if ( w->right->color == 'b' && w->left->color == 'b' )
			{
				w->color = 'r';
				(*x) = (*x)->father;
			}
			else
			{
				if ( w->left->color == 'b' )
				{
					w->right->color = 'b';
					w->color = 'r';
					*head = TreeRotateLeft(*head, w);
					w = (*x)->father->left;
				}

				w->color = (*x)->father->color;
				(*x)->father->color = 'b';
				w->left->color = 'b';
				*head = TreeRotateRight(*head, (*x)->father);
				*x = *head;
			}
		}
	}

	(*x)->color = 'b';
}

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

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
 
	if ( head == pNil )
		return;

	temp1 = temp2 = head;

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

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

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

Tree *TreeRotateLeft(Tree *head, Tree *node)
{
	Tree *y;

	if ( head == pNil || node == pNil )
		return head;

	if ( node->right == pNil )
		return head;

	y = node->right;
	node->right = y->left;

	if ( y->left != pNil )
	{
		y->left->father = node;
	}

	y->father = node->father;

	if ( node->father == pNil )
	{
		head = y;
	}
	else
	{
		if ( node == node->father->left )
		{
			node->father->left = y;
		}
		else
		{
			node->father->right = y;
		}
	}

	y->left = node;
	node->father = y;

	return head;
}

Tree *TreeRotateRight(Tree *head, Tree *node)
{
	Tree *y;

	if ( head == pNil || node == pNil )
		return head;

	if ( node->left == pNil )
		return head;

	y = node->left;
	node->left = y->right;

	if ( y->right != pNil )
	{
		y->right->father = node;
	}

	y->father = node->father;

	if ( node->father == pNil )
	{
		head = y;
	}
	else
	{
		if ( node == node->father->right )
		{
			node->father->right = y;
		}
		else
		{
			node->father->left = y;
		}
	}

	y->right = node;
	node->father = y;

	return head;
}

void TreeSuccessor(Tree *current, Tree **result)
{
	Tree *nodo = current;

	*result = pNil;

	if ( nodo == pNil )
		return;

	if ( nodo->right != pNil )
	{
		nodo = nodo->right;
		while ( nodo != pNil )
		{
			*result = nodo;
			nodo = nodo->left;
		}
	}
	else
	{
		*result = nodo->father;
		while ( *result != pNil && nodo == (*result)->right )
		{
			nodo = *result;
			*result = (*result)->father;
		}
	}
}

void TreePredecessor(Tree *current, Tree **result)
{
	Tree *nodo = current;

	*result = pNil;

	if ( nodo == pNil )
		return;

	if ( nodo->left != pNil )
	{
		nodo = nodo->left;
		while ( nodo != pNil )
		{
			*result = nodo;
			nodo = nodo->right;
		}
	}
	else
	{
		*result = nodo->father;
		while ( *result != NULL && nodo == (*result)->left )
		{
			nodo = *result;
			*result = (*result)->father;
		}
	}
}

void ReverseInOrder(Tree *head)
{
	Tree *temp;

	Tree *stack[MAX_STACK];
	int top;
	top = -1;

	if ( head == pNil )
		return;

	temp = head;

	while ( 1 )
	{
		if ( temp != pNil )
		{
			if ( top < MAX_STACK ) 
			{
				stack[++top] = temp; // Push
				temp = temp->right;
			}
			else
			{
				printf("Errore: lo stack e' pieno.\n");
				return;
			}
		}
		else
		{
			if ( top >= 0 )
			{
				temp = stack[top--]; // Pop 
				printf("%d\n", temp->data);			
				temp = temp->left;
			}
			else
			{
				break;
			}
		}
	}
}

void InOrder(Tree *head)
{
	Tree *temp;

	Tree *stack[MAX_STACK];
	int top;
	top = -1;

	if ( head == pNil )
		return;

	temp = head;

	while ( 1 )
	{
		if ( temp != pNil )
		{
			if ( top < MAX_STACK ) 
			{
				stack[++top] = temp; // Push
				temp = temp->left;
			}
			else
			{
				printf("Errore: lo stack e' pieno.\n");
				return;
			}
		}
		else
		{
			if ( top >= 0 )
			{
				temp = stack[top--]; // Pop 
				printf("%d\n", temp->data);			
				temp = temp->right;
			}
			else
			{
				break;
			}
		}
	}
}

void PreOrder(Tree *head)
{
	Tree *temp;

	Tree *stack[MAX_STACK];
	int top;
	top = 0;

	if ( head == pNil )
		return;

	temp = head;

	stack[top++] = temp; // Push

	while ( top != 0 )
	{
		temp = stack[--top]; // Pop

		printf("%d\n", temp->data);

		if ( temp->right != pNil )
			stack[top++] = temp->right;
		if ( temp->left != pNil )
			stack[top++] = temp->left;
	} 
}

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

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
 
	if ( head == pNil )
		return;

	temp1 = temp2 = head;

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

		while ( (temp1 != pNil) && (temp1->right == pNil || temp1->right == temp2) )
		{
			printf("%d\n", temp1->data);
			temp2 = temp1;
			if ( top == 0 )
				return;
			temp1 = stack[--top]; // Pop
		}

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

void SearchFirst(Tree *head, Tree **result, int key)
{
	Tree *node;

	*result = pNil;
	node = head;

	if ( head == pNil )
		return;

	while( 1 )
	{
		if ( key < node->data )
		{
			if ( node->left == pNil )
				break;
			node = node->left;
		}
		else if ( key > node->data )
		{
			if ( node->right == pNil )
				break;
			node = node->right;
		}
		else // key == node->data
		{
			*result = node;
			break;
		}
	}
}

void SearchNext(Tree *head, Tree **result, int key)
{
	Tree *node;

	*result = pNil;

	if ( head == pNil )
		return;

	node = head->right;
	if ( node == pNil )
		return;

	while( 1 )
	{
		if ( key < node->data )
		{
			if ( node->left == pNil )
				break;
			node = node->left;
		}
		else if ( key > node->data )
		{
			if ( node->right == pNil )
				break;
			node = node->right;
		}
		else // key == node->data
		{
			*result = node;
			break;
		}
	}
}

void TreeMinimum(Tree *head, Tree **result)
{
	Tree *nodo = head;

	*result = pNil;

	if ( nodo == pNil )
		return;

	*result = nodo;

	while ( nodo != pNil )
	{
		*result = nodo;
		nodo = nodo->left;
	}
}

void TreeMaximum(Tree *head, Tree **result)
{
	Tree *nodo = head;

	*result = pNil;

	if ( nodo == pNil )
		return;

	*result = nodo;

	while ( nodo != pNil )
	{
		*result = nodo;
		nodo = nodo->right;
	}
}

int TreeSize(Tree *head)
{
	Tree *temp;
	int sizeLeft, sizeRight;

	Tree *stack[MAX_STACK];
	int top;
	top = -1;

	if ( !head )
		return 0;

	sizeLeft = sizeRight = 0;

	temp = head;

	while ( 1 )
	{
		if ( temp != pNil )
		{
			if ( top < MAX_STACK ) 
			{
				stack[++top] = temp; // Push
				temp = temp->left;
			}
			else
			{
				printf("Errore: lo stack e' pieno.\n");
				return - 1;
			}
		}
		else
		{
			if ( top >= 0 )
			{
				temp = stack[top--]; // Pop 
				if ( temp->data < head->data )
				{
					++sizeLeft;
				}
				else 
				{
					++sizeRight;
				}
				temp = temp->right;
			}
			else
			{
				break;
			}
		}
	}

	//return (sizeLeft + sizeRight + 1);
	return (sizeLeft + sizeRight);
}

int TreeDepth(Tree *head)
{
	Tree *temp1, *temp2;

	int Conta;

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
	Conta = 0;
 
	if ( head == pNil )
	{
		return -1;
	}

	temp1 = temp2 = head;

	while ( temp1 != pNil )
	{
		for(; temp1->left != pNil; temp1 = temp1->left)
		{
			stack[top++] = temp1;
			if ( Conta < top )
				Conta++;
		}

		while ( (temp1 != pNil) && (temp1->right == pNil || temp1->right == temp2) )
		{
			temp2 = temp1;
			if ( top == 0 )
				//return Conta + 1;
				return Conta;
			temp1 = stack[--top];
		}

		stack[top++] = temp1;
		temp1 = temp1->right;
		if ( Conta < top )
			Conta = top;
	}

	//return Conta + 1;
	return Conta + 1;
}

int main()
{
	int k;
	int SearchKey;

	int size;

	int depth;

	Tree *pSearch = NULL;
	Tree *pSuccessor = NULL;
	Tree *pPredecessor = NULL;
	Tree *pTree = NULL;

	InitNil(&pNil);


	pTree = pNil;
	pSearch = pNil;
	pSuccessor = pNil;
	pPredecessor = pNil;

	/*
	pTree = InsertNode(pTree, 21);
	pTree = InsertNode(pTree, 8);
	pTree = InsertNode(pTree, 34);
	pTree = InsertNode(pTree, 55);
	pTree = InsertNode(pTree, 3);
	pTree = InsertNode(pTree, 89);
	pTree = InsertNode(pTree, 5);
	pTree = InsertNode(pTree, 71);
	pTree = InsertNode(pTree, 96);
	*/

	/*
	pTree = InsertNode(pTree, 5);
	pTree = InsertNode(pTree, 4);
	pTree = InsertNode(pTree, 3);
	pTree = InsertNode(pTree, 8);
	pTree = InsertNode(pTree, 34);
	pTree = InsertNode(pTree, 21);
	pTree = InsertNode(pTree, 89);
	//pTree = InsertNode(pTree, 8);
	//pTree = InsertNode(pTree, 8);
	pTree = InsertNode(pTree, 55);
	//pTree = InsertNode(pTree, 8);
	*/

	pTree = InsertNode(pTree, 47);
	pTree = InsertNode(pTree, 59);
	pTree = InsertNode(pTree, 13);
	pTree = InsertNode(pTree, 14);
	pTree = InsertNode(pTree, 15);

	pTree = InsertNode(pTree, 5);
	pTree = InsertNode(pTree, 4);
	pTree = InsertNode(pTree, 3);
	pTree = InsertNode(pTree, 8);
	pTree = InsertNode(pTree, 34);
	pTree = InsertNode(pTree, 21);
	pTree = InsertNode(pTree, 89);
	//pTree = InsertNode(pTree, 8);
	//pTree = InsertNode(pTree, 8);
	pTree = InsertNode(pTree, 55);
	//pTree = InsertNode(pTree, 8);

	pTree = InsertNode(pTree, 27);
	pTree = InsertNode(pTree, 101);
	pTree = InsertNode(pTree, 36);
	pTree = InsertNode(pTree, 102);
	pTree = InsertNode(pTree, 2);

	printf("\nstampa in ordine crescente(inorder):\n");
	InOrder(pTree);

	printf("\nstampa in PreOrder:\n");
	PreOrder(pTree);

	printf("\nstampa in PostOrder:\n");
	PostOrder(pTree);

	printf("\nstampa in ordine decrescente:\n");
	ReverseInOrder(pTree);

	size = TreeSize(pTree);
	printf("\nLa dimensione dell'albero e' -> %d\n", size);

	depth = TreeDepth(pTree);
	printf("\nL'altezza dell'albero e' -> %d\n", depth);


	/*
	printf("\nIl valore della radice, prima della cancellazione e' -> %d\n", pTree->data);
	SearchKey = 21;
	//SearchKey = 5;
	SearchFirst(pTree, &pSearch, SearchKey);
	if ( pSearch != pNil )
	{
		pTree = DeleteNode(pTree, pSearch);
		printf("\nIl valore della radice, dopo la cancellazione e' -> %d\n", pTree->data);
	}
	*/

	//depth = RecursiveTreeDepth(pTree);
	//printf("\nL'altezza dell'albero e' -> %d\n", depth);

	k = -1;
	SearchKey = 8;
	SearchFirst(pTree, &pSearch, SearchKey);
	if ( pSearch != pNil )
		++k;
	while ( pSearch != pNil )
	{
		SearchNext(pSearch, &pSearch, SearchKey);
		++k;
	}
	if ( k < 0)
		k = 0;
	printf("\nTrovate %d occorrenze della chiave %d\n", k, SearchKey);


	pSearch = pNil;
	TreeMinimum(pTree, &pSearch);
	if ( pSearch )
		printf("\nIl valore minimo e' uguale a %d\n", pSearch->data);

	/*
	if ( pSearch->father != pNil )
		printf("\nIl padre del nodo con chiave %d e' il nodo con chiave %d\n", pSearch->data, pSearch->father->data);
	else
		printf("\nIl nodo con chiave %d non ha padre.\n", pSearch->data);
	*/

	pPredecessor = pNil;
	TreePredecessor(pSearch, &pPredecessor);
	if ( pPredecessor != pNil )
		printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
	else
		printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

	pSuccessor = pNil;
	TreeSuccessor(pSearch, &pSuccessor);
	if ( pSuccessor != pNil )
		printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
	else
		printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);

	pSearch = pNil;
	TreeMaximum(pTree, &pSearch);
	if ( pSearch )
		printf("\nIl valore massimo e' uguale a %d\n", pSearch->data);

	/*
	if ( pSearch->father != pNil )
		printf("\nIl padre del nodo con chiave %d e' il nodo con chiave %d\n", pSearch->data, pSearch->father->data);
	else
		printf("\nIl nodo con chiave %d non ha padre.\n", pSearch->data);
	*/

	pPredecessor = pNil;
	TreePredecessor(pSearch, &pPredecessor);
	if ( pPredecessor != pNil )
		printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
	else
		printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

	pSuccessor = pNil;
	TreeSuccessor(pSearch, &pSuccessor);
	if ( pSuccessor != pNil )
		printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
	else
		printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);

	/*
	SearchKey = 89;
	pSearch = pNil;
	SearchFirst(pTree, &pSearch, SearchKey);
	pTree = DeleteNode(pTree, pSearch);
	printf("\nstampa in ordine crescente dopo la cancellazione del nodo con chiave %d :\n", SearchKey);
	InOrder(pTree);
	*/

	/*
	SearchKey = 5;
	pSearch = pNil;
	SearchFirst(pTree, &pSearch, SearchKey);
	pTree = DeleteNode(pTree, pSearch);
	printf("\nstampa in ordine crescente dopo la cancellazione del nodo con chiave %d :\n", SearchKey);
	InOrder(pTree);
	*/


	/*
	SearchKey = 5;
	pSearch = pNil;
	SearchFirst(pTree, &pSearch, SearchKey);

	if ( pSearch != pNil )
	{
		printf("\nIl valore della radice, prima della rotazione a sinistra, e' -> %d\n", pTree->data);

		printf("\nRotazione a sinistra del nodo con chiave %d\n", pSearch->data);
		pTree = TreeRotateLeft(pTree, pSearch);

		printf("Il valore della radice, dopo la rotazione a sinistra, e' -> %d\n", pTree->data);
		printf("Cancellazione della radice %d\n", pTree->data);
		pTree = DeleteNode(pTree, pTree);
	}
	*/

	/*
	if ( pSearch != pNil )
		printf("\nIl valore della radice, prima della rotazione a destra, e' -> %d\n", pTree->data);

	printf("\nRotazione a destra del nodo con chiave %d\n", pSearch->data);
	pTree = TreeRotateRight(pTree, pSearch);

	if ( pSearch != pNil )
		printf("\nIl valore della radice, dopo la rotazione destra, e' -> %d\n", pTree->data);
	*/

	SearchKey = 55;
	pSearch = pNil;
	SearchFirst(pTree, &pSearch, SearchKey);

	if ( pSearch != pNil )
	{
		printf("\nIl valore della radice, prima della cancellazione, e' -> %d\n", pTree->data);

		printf("Cancellazione della radice %d\n", pTree->data);
		pTree = DeleteNode(pTree, pTree);

		//printf("Cancellazione del nodo %d\n", pSearch->data);
		//pTree = DeleteNode(pTree, pSearch);

		printf("\nIl valore della radice, dopo la cancellazione, e' -> %d\n", pTree->data);
	}


	size = TreeSize(pTree);
	printf("\nLa dimensione dell'albero, dopo le operazioni precedenti, e' -> %d\n", size);

	depth = TreeDepth(pTree);
	printf("\nL'altezza dell'albero, dopo le operazioni precedenti, e' -> %d\n", depth);

	//depth = RecursiveTreeDepth(pTree);
	//printf("\nLa profondita' dell'albero, dopo la rotazione a sinistra, e' -> %d\n", depth);

	printf("\nstampa in ordine crescente(inorder):\n");
	InOrder(pTree);

	FreeTree(pTree);
	FreeTree(pNil);

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

	return 0;
}

[strasy]

Grazie per il tuo aiuto.

A me comunque interessava solo la parte in cui bisognava inserire le chiavi dei nodi e tutte le loro info (colore, padre, sinistro e destro)...e poi la parte dei collegamenti tra i nodi...in modo da costruire un albero di base su cui provare le funzioni di inserimento di un nodo, rotazione, rimozione, ecc.

Ma ovviamente non potevo provare le funzioni senza un albero di base costruito...ecco il mio obiettivo.

Non esiste un modo per costruire un albero senza dover inserire le chiavi e i colori all'interno della funzione main(), ma inserendoli di volta in volta durante l'esecuzione del programma? si dovrebbero fare dei cicli...sull'allocazione della memoria dei nodi ci sono, ma mi viene difficile collegare i nodi tra loro...poichè come indico ad esempio il nodo padre?

Comunque, per il momento sono riuscita a provare le mie funzioni...