codice:
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);
}
int isTriangular(Tree *head)
{
static int isTriang = 1;
static int lDepth = 0;
static int rDepth = 0;
if ( !head )
{
return 0;
}
else
{
if ( (head->left && !(head->right)) || (head->right && !(head->left)) )
isTriang = 0;
isTriangular(head->left);
isTriangular(head->right);
if (lDepth > rDepth)
{
lDepth++;
return isTriang;
}
else
{
rDepth++;
return isTriang;
}
}
}
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;
temp1 = stack[--top];
}
stack[top++] = temp1;
temp1 = temp1->right;
if ( Conta < top )
Conta = top;
}
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, 47);
pTree = InsertNode(pTree, 59);
pTree = InsertNode(pTree, 14);
pTree = InsertNode(pTree, 15);
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);
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);
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);
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 = 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("\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);
printf("\nstampa in ordine crescente(inorder):\n");
InOrder(pTree);
if ( isTriangular(pTree) )
printf("\nL'albero e' triangolare!\n");
else
printf("\nL'albero non e' affatto triangolare!!!\n");
FreeTree(pTree);
FreeTree(pNil);
return 0;
}
Rispondi quotando