PDA

Visualizza la versione completa : -- Algoritmo di ricerca binario


silverfox5010
27-09-2008, 23:09
Salve !
Trovo difficoltà con l' ordine dei nodi del seguente grafico :

http://i36.tinypic.com/5flxmb.gif

Il nodo 0 ha nodi figli 1 e 2 :
il nodo 2 ha figli 3 e 5

Il nodo 2 ha nodi figli 3 e 5 : il nodo 3 ha nodo figlio 4
il nodo 5 ha nodo figlio 8

Il nodo 8 ha nodo figli 6 e 10 :
il nodo 6 ha nodo figlio 7
il nodo 10 ha nodi figli 9 e 11


Questa è la mia interpretazione. Però l' ordine dei nodi non è crescente.
Qualcuno mi può spiegare il grafico gentilmente ? Sò che è una richiesta banale però..
Grazie in anticipo !

menphisx
28-09-2008, 03:01
Bah scritto così dall'alto verso il basso, sembrerebbe di più che:
Il nodo 5 ha figli i nodi 2, 8
Il nodo 2 ha figli i nodi 0, 3
Il nodo 0 ha figlio il nodo 1
Il nodo 3 ha figlio il nodo 4
Il nodo 8 ha figli i nodi 6, 10
Il nodo 6 ha figlio il nodo 7
Il nodo 10 ha figli i nodi 9, 11

Se si segue l'ordine numerico, la tua interpretazione è corretta.

:ciauz:

silverfox5010
28-09-2008, 13:00
Grazie per la risposta. Ciò che non capisco è appunto l' ordine perchè di solito
è in modo crescente, partendo dal nodo di sinistra a quello più a destra, tipo :



0
/ \
1 2
/ \ / \
3 4 5 6



mentre nel caso sopra, abbiamo ad esempio che il nodo 2 ha nodi figli 3 e 5 e non 3 e 4.
Humm..

oregon
28-09-2008, 13:40
E' un albero binario ordinato (sequenza inorder).

Gli elementi di valore minore stanno nei sottoalberi sinistri, quelli maggiori a destra.

Vai sempre a sinistra ... poi a destra se puoi, e risali ...

silverfox5010
28-09-2008, 16:29
Grazie a tutti :D ! Mi sono reso conto come si leggesse grazie al vostro aiuto finalmente.

Loading