[c] Binary tree

[beppegrillo]

Qualcuno mi indicherebbe un algoritmo ricorsivo per ottenere il nodo con chiave massima da un albero binario (non di ricerca).

tnx.

[sottovento]

La prima cosa che mi viene in mente.
Attenzione - si incarta, (direi ovviamente) se si passa in ingresso un albero nullo.


// NOTICE - root MUST be != NULL
BinTree *getMaxNode (BinTree *root)
{
BinTree *p, *q;

// If root is leaf, then it is the maximum
if (!root->left && !root->right) return root;
p = root;
if (root->left)
{
q = getMaxNode (root->left);
p = (q->value > p->value) ? q : p;
}
if (root->right)
{
q = getMaxNode (root->right);
p = (q->value > p->value) ? q : p;
}
return p;
}

[sottovento]

... omissis ...

int InitGetValue (btree *root)
{
int left_val, right_val;

if (!root) {
printf ("\nAlbero vuoto\n");
system("pause");
exit(1);
}

if (!(root->left || root->right))
return root->value;

if (root->left)
left_val = GetValue(root->left);
if (root->right)
right_val = GetValue(root->right);

if (left_val >= right_val) // Attenzione: vai a confrontare due elementi, uno dei quali potrebbe non avere un valore!!! (Esempio: root->right == NULL)
if (left_val >= root->value)
return left_val;
else return root->value;
else if (right_val >= root->value)
return right_val;
else return root->value;
}
... omissis...


... omissis ...


Un'altra soluzione potrebbe essere l'uso di una variabile globale, qualcosa del tipo:


void getTreeMax (BinTree *root)
{
if (!gPointMax) gPointMax = root;
if (root)
{
if (root->value > gPointMax->value) gPointMax = root;
getTreeMax (root->left);
getTreeMax (root->right);
}
}


L'unico problema e' che occorre assegnare il valore iniziale a gPointMax prima di chiamare questa procedura. Al termine della ricorsione, gPointMax conterra' il puntatore all'elemento contenente la chiave maggiore, oppure NULL se l'albero era vuoto.
La chiamata percio' sara' qualcosa del tipo:


gPointMax = NULL;
getMaxTree (root);


L'uso di questi trucchetti pero' a lungo andare (i.e. in un programma di grandi dimensioni) potrebbe risultare controproducente....

[71104]

se gli alberi contengono solo valori postivi:

int TreeMax(PTREE Tree) {
if (!Tree) {
return 0;
}

int Result = Tree->Value;

int LeftMax = TreeMax(Tree->Left);
if (LeftMax > Result) {
Result = LeftMax;
}

int RightMax = TreeMax(Tree->Right);
if (RightMax > Result) {
Result = RightMax;
}

return Result;
}

[beppegrillo]

credo che la soluzione più elegante sia quella data da 71104.