Albero

[enigmagame]

Ciao
Voi come risolvereste questo problema?
Si scriva il pseudo-codice di una programma che, preso in input un numero non negativo N, produca un albero binario quasi bilanciato con N nodi.
Ciao!!!

[giacor86]

se mi dici cs'è un albero binario quasi bilanciato........

[enigmagame]

Ciao
i nodi dell’ultimo livello sono addossati a sinistra, definizione molto semplice...
Idee?

[gigilatrottola2]

Dunque, un BST è bilanciato se le sue foglie hanno la stessa altezza.

Per crearlo il suggerimento è questo.
Se lavori sugli Alberi di ricerca sicuramente avrai pastrocchiato con gli algoritmi di ordinamento, quindi probabilmente conoscerai il Mergesort.

Il corpo vero e proprio sono 4-5 righe in tutto (è ricorsivo). Ecco devi farne una lieve modifica in modo tale che l'algoritmo peschi di volta in volta il valore di mezzo dell'insieme degli N valori. Cosi facendo l'albero viene bilanciato.

[enigmagame]

Ciao
Secondo te una cosa cosi potrebbe avere senso?

Make_Tree(int N)
nodo = new_node(N);
N--;
nodo.left = Make_Tree(N/2);
nodo.right = Make_Tree(N/2);

new_node e' un costruttore di un nuovo nodo, con una chiave un puntatore a sx e uno a dx.
Ciao