ecco il mio problema ... non ho ben capito una cosa sugli alberi binari! cioè come fare uno schema su carta ................
prendendo questi valori nell'ordine che segue, come vanno disposti nell'albero binario (tale che il valore di un nodo sia maggiore di tutti quelli nel suo sottoalbero sinistro e minore di quelli del sottoalbero destro)??
104, 32, 44, 121, 200, 152, 23
L'albero risultante del tuo esempio è il seguente :
codice:104 / \ 32 152 / \ / \ 23 44 121 200
invece il mio libro lo fa cosi ...
ma è sbagliato ... no?! che cacchio di libro ....codice:104 / \ 32 121 / \ \ 23 44 200 / 152
no. non è sbagliato.
la definizione di albero binario dice solo che a parte laregola che ha menzionato sull'oridnamento,
ogni nodo ha, al più due figli.
Al limite quello che disegna il tuo libro è un albero binario NON bilanciato.
anzi, quello del tuo libro è quello corretto se sui la sequenza dell'esempio
la procedura:
il primo n è 104, per cui è la radice dell'albero.
il secondo è 32, (< di 104) quindi è il figlio sinistro.
poi c'è 44 (< di 104) e va a sinistra, è > di 32 e quindi diventa il filgio di destra di 32. e cosi' via.
quindi per inserire ogni elemento, si rivaluta l'albero dall'inizio ... si riparte dalla radice, giusto?
si esatto. l'unico "punto di accesso" dell'albero binario è la radice, ogni inserimento parte da li'.
Ovviamente questa tecina puo' portare ad avere alberi fortemente sbilanciati.
Il caso degenere è quello di avere una lista, se la sequenza di ingresso è ordinata.
Ad esempio, prova con:1 2 3 4 5
ovvio si avrebbe un albero di livello 5
capito capito ... ora è tutto estremamente più chiaro
Permessi di invio
Rispondi quotando