[C] Alberi binari

[sam333]

Ciao a tutti:D ,sto cercando di capire come creare alberi binari in c,qualcuno sa spiegarmi bene come funzionano?anche con un esempio molto semplice....so che ci vuole una struttura dati come per le liste e che bisogna usare la ricorsione,ma fino ad ora tutti i miei sforzi non sono serviti a niente:mbe:

[sam333]

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


struct nodi{


int num;
struct nodi *sx,*dx;


};


struct nodi *crea_albero(int n){

if(n==0){


return NULL;

}
else{

struct nodi *a=(struct nodi*)malloc(sizeof(struct nodi));
int sx,dx;
int numero;
printf("Inserire numero--> ");
scanf("%d",&a->num);
sx=n/2;
dx=n-sx-1;

a->sx=crea_albero(sx);
a->dx=crea_albero(dx);
return a;
}


}

void leggi(struct nodi *a){


while(a!=NULL){


printf("%d\n",a->num);
leggi(a->sx);
leggi(a->dx);

}


}
int main(){


int num;
struct nodi *a;
printf("Quanti nodi vuoi creare?--> ");
scanf("%d",&num);
a=crea_albero(num);
leggi(a);
}



ho scritto questo codice...ho preso spunto da un esempio su internet ma quando vado a visualizzare il tutto esce solo il primo numero ripetuto:muro:

[Vincenzo1968]

Ah gli alberi binari, bell'argomento. Bello e utile. ;)

Domani ti spiego tutto quanto. Ora sono troppo stanco; ho combattuto tutto il giorno col contest 19.
Domani ti posto l'implementazione in C degli algoritmi sull'argomento illustrati nel Cormen. ;)

Domani li svisceriamo a fondo gli alberi binari: dalla versione più semplice fino alle versioni più avanzate: Red-Black, 2-3-4, etc.

;)

[sam333]

grazie mille!!:D io intanto provo a capirci qualcosa in più:)

[sottovento]

void leggi(struct nodi *a)
{
while(a!=NULL)
{
printf("%d\n",a->num);
leggi(a->sx);
leggi(a->dx);
}
}



Trattasi di loop infinito, in quanto il valore di a non cambiera' mai; pertanto il ciclo while non avra' mai fine.

Ad ogni modo, riparare questo codice e' semplice: siccome stai gia' usando la ricorsione per la scansione dell'albero, non abbisogni del ciclo while.
Semplicemente sostituisci if a while e dovrebbe essere a posto

[Vincenzo1968]

Intanto posto una versione iterativa degli alberi binari di ricerca:

Versione iterativa(cioè non ricorsiva):

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

#define MAX_STACK 512

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

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

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

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);
void TreeSuccessor(Tree *current, Tree **result);
void TreePredecessor(Tree *current, Tree **result);
Tree *TreeRotateLeft(Tree *head, Tree *node);
Tree *TreeRotateRight(Tree *head, Tree *node);
int TreeSize(Tree *head);
int TreeDepth(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->father = NULL;
r->left = NULL;
r->right = NULL;

return r;
}

Tree *InsertNode(Tree *node, int key)
{
Tree *pRadice = NULL;

if( !node )
{
node = NewNode(key);
printf("Creo la radice e inserisco il primo numero: %d\n", key);
return node;
}

pRadice = node;

while( 1 )
{
if ( key < node->data )
{
if ( !node->left )
{
node->left = NewNode(key);
node->left->father = node;
printf("Inserisco %d a sinistra di %d\n", key, node->left->father->data);
break;
}
node = node->left;
}
else
{
if ( !node->right )
{
node->right = NewNode(key);
node->right->father = node;
printf("Inserisco %d a destra di %d\n", key, node->right->father->data);
break;
}
node = node->right;
}
}

node = pRadice;

return node;
}

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

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

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

if ( y->left != NULL )
{
x = y->left;
}
else
{
x = y->right;
}

if ( x != NULL )
{
x->father = y->father;
}

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

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

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

return root;
}

/*
void FreeTree(Tree *root)
{
if(!root)
return;

FreeTree(root->left);
FreeTree(root->right);
if( root->data )
free(root);
}
*/

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

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
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;
}
}

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

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

if ( !head )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
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 )
return;

temp = head;

while ( 1 )
{
if ( temp != NULL )
{
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 )
return;

temp = head;

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

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

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

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

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

Tree *stack[MAX_STACK];
int top;

top = 0;

if ( !head )
return;

temp1 = temp2 = head;

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

while ( (temp1 != NULL) && (temp1->right == NULL || 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 = NULL;
node = head;

if ( !head )
return;

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

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

*result = NULL;

if ( !head )
return;

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

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

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

*result = NULL;

if ( !nodo )
return;

*result = nodo;

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

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

*result = NULL;

if ( !nodo )
return;

*result = nodo;

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

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

*result = NULL;

if ( !nodo )
return;

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

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

*result = NULL;

if ( !nodo )
return;

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

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

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

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

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

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

y->father = node->father;

if ( node->father == NULL )
{
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 == NULL || node == NULL )
return head;

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

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

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

y->father = node->father;

if ( node->father == NULL )
{
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;
}

/*
int TreeSize(Tree *head)
{
if ( head == NULL )
{
return 0;
}
else
{
return ( TreeSize(head->left) + 1 + TreeSize(head->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 != NULL )
{
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 RecursiveTreeDepth(Tree* head)
{
//int lDepth = -1;
//int rDepth = -1;

if ( head == NULL)
{
return -1;
}
else
{
int lDepth = RecursiveTreeDepth(head->left);
int rDepth = RecursiveTreeDepth(head->right);

if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
*/

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

int Conta;

Tree *stack[MAX_STACK];
int top;

top = 0;
Conta = 0;

if ( head == NULL )
{
return -1;
}

temp1 = temp2 = head;

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

while ( (temp1 != NULL) && (temp1->right == NULL || 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;

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, 55);

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);

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

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

pPredecessor = NULL;
TreePredecessor(pSearch, &pPredecessor);
if ( pPredecessor != NULL )
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 = NULL;
TreeSuccessor(pSearch, &pSuccessor);
if ( pSuccessor != NULL )
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 = NULL;
TreeMaximum(pTree, &pSearch);
if ( pSearch )
printf("\nIl valore massimo e' uguale a %d\n", pSearch->data);

pPredecessor = NULL;
TreePredecessor(pSearch, &pPredecessor);
if ( pPredecessor != NULL )
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 = NULL;
TreeSuccessor(pSearch, &pSuccessor);
if ( pSuccessor != NULL )
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 = 5;
pSearch = NULL;
SearchFirst(pTree, &pSearch, SearchKey);

if ( pSearch != NULL )
{
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);
}

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);

FreeTree(pTree);

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

return 0;
}


Questo è l'output:

Creo la radice e inserisco il primo numero: 47
Inserisco 59 a destra di 47
Inserisco 13 a sinistra di 47
Inserisco 14 a destra di 13
Inserisco 15 a destra di 14
Inserisco 5 a sinistra di 13
Inserisco 4 a sinistra di 5
Inserisco 3 a sinistra di 4
Inserisco 8 a destra di 5
Inserisco 34 a destra di 15
Inserisco 21 a sinistra di 34
Inserisco 89 a destra di 59
Inserisco 55 a sinistra di 59
Inserisco 27 a destra di 21
Inserisco 101 a destra di 89
Inserisco 36 a destra di 34
Inserisco 102 a destra di 101
Inserisco 2 a sinistra di 3

stampa in ordine crescente(inorder):
2
3
4
5
8
13
14
15
21
27
34
36
47
55
59
89
101
102

stampa in PreOrder:
47
13
5
4
3
2
8
14
15
34
21
27
36
59
55
89
101
102

stampa in PostOrder:
2
3
4
8
5
27
21
36
34
15
14
13
55
102
101
89
59
47

stampa in ordine decrescente:
102
101
89
59
55
47
36
34
27
21
15
14
13
8
5
4
3
2

La dimensione dell'albero e' -> 18

L'altezza dell'albero e' -> 6

Trovate 1 occorrenze della chiave 8

Il valore minimo e' uguale a 2

Il nodo con chiave 2 non ha predecessore.

Il successore del nodo con chiave 2, e' il nodo con chiave 3

Il valore massimo e' uguale a 102

Il predecessore del nodo con chiave 102, e' il nodo con chiave 101

Il nodo con chiave 102 non ha successore.

Il valore della radice, prima della rotazione a sinistra, e' -> 47

Rotazione a sinistra del nodo con chiave 5
Il valore della radice, dopo la rotazione a sinistra, e' -> 47
Cancellazione della radice 47

La dimensione dell'albero, dopo le operazioni precedenti, e' -> 17

L'altezza dell'albero, dopo le operazioni precedenti, e' -> 6

stampa in ordine crescente(inorder):
2
3
4
5
8
13
14
15
21
27
34
36
55
59
89
101
102

[sam333]

Noto che però è un po complicato :mbe:

[misterx]

Noto che però è un po complicato :mbe:

ti conviene prima leggere un pò di teoria altrimenti non ne esci, gli alberi binari sono molto efficienti ma richiedono un briciolo di impegno. Ti consiglio di imparare le cose step by step evitando di impazzire con codice eccessivamente lungo e per nulla commentato. Cosa studi per curiosità ?


http://it.wikipedia.org/wiki/Albero_binario

[Vincenzo1968]

Noto che però è un po complicato :mbe:

Pazienta Sam, che adesso arrivano le spiegazioni. Cominceremo dalla versione più semplice, quella terra terra, degli alberi binari. Per il momento conservati il codice che ti ho postato che ha un sacco di utili caratteristiche.

;)

E comunque, la versione che ho postato, è una versione particolare di albero binario: albero binario di ricerca: BST, Binary Search Tree. La vedremo meglio(e nei particolari), più in la. ;)

[Vincenzo1968]

Una versione di albero binario normale. Il codice l'avevo scritto per un utente che qui aveva chiesto come verificare se l'albero è triangolare o meno:


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

#define MAX_STACK 4096

//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");

//printf("\nAltezza albero 1: %d\n", isTriangular(pTree1));

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


Più tardi le spiegazioni. ;)

[sam333]

ok provo a studiarmi quest'ultimo codice intanto..

[Vincenzo1968]

Aspetta, aspetta!

Questa è una versione ancora più semplice:


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

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);
void printTree(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)
{
if(!head)
return;

FreeTree(head->left);
FreeTree(head->right);
if( head )
{
free(head);
MemoriaDeallocata += sizeof(Tree);
}
}

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

void printTree(Tree *head)
{
if ( head == NULL )
return;

printTree(head->left);
printf("%d ", head->data);
printTree(head->right);
}

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);

printf("\nAlbero 1: ");
printTree(pTree1);
printf("\nAlbero 2: ");
printTree(pTree2);
printf("\n");

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


Utilizzo una versione ricorsiva(e quindi più compatta, più corta ;) ) per liberare la memoria in FreeTree.

Per ora fregatene della funzione IsTriangular. Cerca di capire come viene costruito l'albero. ;)

http://img37.imageshack.us/img37/5192/triangtree2.jpg

[Vincenzo1968]

Beccati anche la versione semplice semplice, senza la ricerca della triangolazione. La versione ridotta all'osso:


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

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);
void printTree(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)
{
if(!head)
return;

FreeTree(head->left);
FreeTree(head->right);
if( head )
{
free(head);
MemoriaDeallocata += sizeof(Tree);
}
}

void printTree(Tree *head)
{
if ( head == NULL )
return;

printTree(head->left);
printf("%d ", head->data);
printTree(head->right);
}

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);

printf("\nAlbero 1: ");
printTree(pTree1);
printf("\nAlbero 2: ");
printTree(pTree2);
printf("\n");

FreeTree(pTree1);
FreeTree(pTree2);

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

return 0;
}


;)

http://img850.imageshack.us/img850/3806/simpletree.jpg

[sam333]

ok allora parto dall'ultimo codice.... ti faccio sapere....ah intanto grazie per l aiuto:D

[Vincenzo1968]

ok allora parto dall'ultimo codice.... ti faccio sapere....ah intanto grazie per l aiuto:D

Di niente ;)

Anzi scusa se ancora non ho postato le spiegazioni promesse ma sono impegnato su più fronti: lavoro e, soprattutto, debbo asfaltare Vicius nel contest 19. :D

Ma arriveranno anche quelle(le spiegazioni, dico) ;)

[banryu79]

Ad un certo punto potresti raccogliere le spiegazioni e il codice che qui pubblichi in un tutorial che potresti proporre perchè sia pubblicato nella sezione "Tutorials" di qesta sezione del forum.

A lungo termine potrebbe essere utile a molti neofiti, come vari tutorials si sono dimostrati esserlo.

[sam333]

quindi in questo modo si crea un nodo con i due"rami"uno che va a sinistra e l'altro a destra che a loro volta hanno due rami?oppure si crea solo un nodo con due rami e basta e per ora siamo fermi lì?nono tranquillo anzi mi stai già aiutando tanto,

[Vincenzo1968]

Ad un certo punto potresti raccogliere le spiegazioni e il codice che qui pubblichi in un tutorial che potresti proporre perchè sia pubblicato nella sezione "Tutorials" di qesta sezione del forum.

A lungo termine potrebbe essere utile a molti neofiti, come vari tutorials si sono dimostrati esserlo.

Vero è. In fondo si tratta di codice che avevo scritto per la pubblicazione del miei articoli quando avevo il sito guidealgoritmi.it.

:D

[Vincenzo1968]

quindi in questo modo si crea un nodo con i due"rami"uno che va a sinistra e l'altro a destra che a loro volta hanno due rami?oppure si crea solo un nodo con due rami e basta e per ora siamo fermi lì?nono tranquillo anzi mi stai già aiutando tanto,

Puoi capirlo da qui:

pTree1 = NewNode(1);
pTree1->left = NewNode(2);
pTree1->right = NewNode(3);
pTree1->left->left = NewNode(4);
pTree1->left->right = NewNode(5);


la prima istruzione crea la radice, il nodo contenente il valore 1.
La seconda istruzione crea il nodo figlio sinistro del nodo radice e vi piazza il valore 2, e così via.

Il codice andrebbe sistemato meglio in modo da fargli controllare che un nodo non sia NULL prima di utilizzarlo. Lo vedremo meglio più avanti(quando avrò definitivamente asfaltato Vicius) :D

[sam333]

ma nel primo codice che ho fatto aggiungo prima i nodi a sinistra e poi quelli a destra giusto?però i nodi "intermedi" di sinistra per esempio non puntano a nessun nodo a destra giusto?

[Vincenzo1968]

Sam, ti ho modificato il codice:

http://img339.imageshack.us/img339/3806/simpletree.jpg

Così dovrebbe risultare più chiaro come viene costruito l'albero.

Ecco:


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

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);
void printTree(Tree *head);
int makeTree(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)
{
if(!head)
return;

FreeTree(head->left);
FreeTree(head->right);
if( head )
{
free(head);
MemoriaDeallocata += sizeof(Tree);
}
}

void printTree(Tree *head)
{
if ( head == NULL )
return;

printTree(head->left);
printf("%d ", head->data);
printTree(head->right);
}

int makeTree(Tree **head)
{
printf("Costruisco la radice: root(1)\n");
*head = NewNode(1);
if ( !(*head) )
return 0;

printf("Costruisco il nodo figlio: root(1)->left(2)\n");
(*head)->left = NewNode(2);
if ( !((*head)->left) )
return 0;

printf("Costruisco il nodo figlio: root(1)->right(3)\n");
(*head)->right = NewNode(3);
if ( !((*head)->right) )
return 0;

printf("Costruisco il nodo figlio: root(1)->left(2)->left(4)\n");
(*head)->left->left = NewNode(4);
if ( !((*head)->left->left) )
return 0;

printf("Costruisco il nodo figlio: root(1)->left(2)->right(5)\n");
(*head)->left->right = NewNode(5);
if ( !((*head)->left->right) )
return 0;

printf("Costruisco il nodo figlio: root(1)->right(3)->left(6)\n");
(*head)->right->left = NewNode(6);
if ( !((*head)->right->left) )
return 0;

printf("Costruisco il nodo figlio: root(1)->right(3)->right(7)\n");
(*head)->right->right = NewNode(7);
if ( !((*head)->right->right) )
return 0;

printf("Costruisco il nodo figlio: root(1)->left(2)->left(4)->left(8)\n");
(*head)->left->left->left = NewNode(8);
if ( !((*head)->left->left->left) )
return 0;

printf("Costruisco il nodo figlio: root(1)->left(2)->left(4)->right(9)\n");
(*head)->left->left->right = NewNode(9);
if ( !((*head)->left->left->right) )
return 0;

return 1;
}

int main()
{
Tree *pTree1 = NULL;

printf("\n");

if ( !makeTree(&pTree1) )
{
printf("\nImpossibile costruire l'albero per memoria insufficiene o chissa' che altro. Addio!\n");
if ( pTree1 )
FreeTree(pTree1);
return -1;
}

printf("\nAlbero : ");
printTree(pTree1);

FreeTree(pTree1);

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

return 0;
}


;)

[Vincenzo1968]

Ma nel primo codice che ho fatto aggiungo prima i nodi a sinistra e poi quelli a destra, giusto? Però i nodi "intermedi" di sinistra, per esempio, non puntano a nessun nodo a destra, giusto?

Boh! Domani mattina, a mente fresca, vediamo. ;)

[Vincenzo1968]

http://img339.imageshack.us/img339/3806/simpletree.jpg

Costruisco la radice: root(1)
http://img832.imageshack.us/img832/9145/step01g.jpg

Costruisco il nodo figlio: root(1)->left(2)
http://img689.imageshack.us/img689/6484/step02.jpg

Costruisco il nodo figlio: root(1)->right(3)
http://img407.imageshack.us/img407/2266/step03.jpg

Costruisco il nodo figlio: root(1)->left(2)->left(4)
http://img585.imageshack.us/img585/1596/step04.jpg

Costruisco il nodo figlio: root(1)->left(2)->right(5)
http://img189.imageshack.us/img189/8936/step05h.jpg

Costruisco il nodo figlio: root(1)->right(3)->left(6)
http://img19.imageshack.us/img19/3605/step06p.jpg

Costruisco il nodo figlio: root(1)->right(3)->right(7)
http://img818.imageshack.us/img818/8994/step07.jpg

Costruisco il nodo figlio: root(1)->left(2)->left(4)->left(8)
http://img843.imageshack.us/img843/8747/step08.jpg

Costruisco il nodo figlio: root(1)->left(2)->left(4)->right(9)
http://img651.imageshack.us/img651/435/step09.jpg

;)

[sam333]

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





struct nodi{

int info;

struct nodi *sx,*dx;


};
typedef struct nodi nodo;


///Elenco funzioni...
nodo *crea_alb();
nodo *crea_nodo(nodo *a,int x);
void stampa(nodo *a);
void free_nodo(nodo *a);

///Main..
int main(){

nodo *radice;

radice=crea_alb();
stampa(radice);
free(radice);
}








///Creo albero..

nodo *crea_alb(){


nodo *alb=NULL;
nodo *a;


do{


printf("Inserire elemento--> ");
scanf("%d",&a->info);
if(a->info!=0){


alb=crea_nodo(alb,a->info);

}

}
while(a->info!=0);
return alb;
}





///Creo nodi..


nodo *crea_nodo(nodo *a,int x){



if(a==NULL){
a=(nodo*)malloc(sizeof(nodo));
a->info=x;
a->sx=NULL;
a->dx=NULL;


}
else {
if(x<a->info)

a->sx=crea_nodo(a->sx,x);



else if(x>a->info)
a->dx=crea_nodo(a->dx,x);

}


return a;
}



void stampa(nodo*a){

if(a!=NULL){


printf("%d\n\n",a->info);
stampa(a->sx);
stampa(a->dx);

}

}


void free_nodo(nodo *a){


if(!a){

free(a->sx);
free(a->dx);


}
if(a){


free(a);
}


}




ho fatto questo codice come logica l albero dovrebbe venire così:



io inserisco 6-12-30-150-60-400-77

output: 6-12-30-150-60-77-400


quindi l'albero dovrebbe essere così..


http://imageshack.us/a/img12/5460/alberoyg.jpg

[Vincenzo1968]

Sam se non indenti meglio il codice non si capisce niente. E non lasciare tutte quelle righe vuote. Al massimo una riga vuota per separare le istruzioni.

;)

[sam333]

Scusa:doh: va meglio così?

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


///CREO LA STRUTTURA

struct nodi{

int info;

struct nodi *sx,*dx;


};
typedef struct nodi nodo;



///CREO L'ALBERO..

nodo *crea_alb(){


nodo *alb=NULL;
nodo *a;


do{

printf("Inserire elemento--> ");
scanf("%d",&a->info);
if(a->info!=0){

alb=crea_nodo(alb,a->info);

}

}
while(a->info!=0);
return alb;
}


///CREO I NODI


nodo *crea_nodo(nodo *a,int x){

//se il nodo è NULL lo creo

if(a==NULL){
a=(nodo*)malloc(sizeof(nodo));
a->info=x;
a->sx=NULL;
a->dx=NULL;
}
else {
if(x<a->info)

a->sx=crea_nodo(a->sx,x);

else if(x>a->info)
a->dx=crea_nodo(a->dx,x);

}

return a;
}




void stampa(nodo*a){

if(a!=NULL){

printf("%d\n\n",a->info);
stampa(a->sx);
stampa(a->dx);

}

}
///LIBERO LA MEMORIA ALLOCATA

void free_nodo(nodo *a){


if(!a){

free(a->sx);
free(a->dx);


}
if(a){

free(a);
}
}



int main(){

nodo *radice;

radice=crea_alb();
stampa(radice);
free(radice);
}