Un albero binario perfetto (chiamato anche un albero binario completo nel senso che tutti i livelli sono pieni) mostra le seguenti caratteristiche:
1. Tutti i nodi interni hanno esattamente due bambini: Ogni nodo che non è un nodo foglia deve avere un bambino sinistro e un bambino destro.
2. Tutti i nodi fogliare sono allo stesso livello: La profondità di tutti i nodi fogliare (nodi senza bambini) è identica. Ciò significa che l'albero è perfettamente bilanciato.
3. Il numero di nodi a livello `i` è` 2^i`: Dove il livello di radice è considerato il livello 0.
4. Il numero totale di nodi in un albero binario perfetto di altezza `h` è` 2^(h+1) - 1` .
5. Altezza di un albero binario perfetto con `n` nodi è` log2 (n+1) - 1` . Questo è spesso approssimato come `log2 (n)`.
Implicazioni di queste caratteristiche:
* Un albero binario perfetto è intrinsecamente equilibrato.
* La sua struttura è altamente prevedibile e regolare.
* È altamente efficiente dal punto di vista spazio, con una memoria minima sprecata a causa di nodi non riempiti.
Ecco come potresti implementare un albero binario perfetto in Java, concentrandosi su una struttura di base e le operazioni chiave:
`` `Java
class PerfectBinaryTree {
nodo di classe statica {
Int Data;
Nodo a sinistra;
Nodo a destra;
Nodo (int data) {
this.data =data;
this.left =null;
this.right =null;
}
}
Radice di nodo;
Altezza int; // Altezza dell'albero (numero di livelli - 1)
public PerfectBinaryTree (Int Height) {
this.height =altezza;
this.root =costructPerFectBinaryTree (0, altezza);
}
nodo privato ConstructPerFectBinaryTree (int currentlevel, int maxheight) {
if (currentlevel> maxheight) {
restituire null;
}
// Crea un nodo
Nodo nodo =nuovo nodo ((int) math.pow (2, currentlevel)); // Esempio:usa il livello 2^come valore nodo
// Crea ricorsivamente i sottostrutici sinistra e destra
node.left =costructPerFectBinaryTree (Currentlevel + 1, MaxHeight);
node.right =costructPerFectBinaryTree (Currentlevel + 1, MaxHeight);
nodo di ritorno;
}
// Esempio:in ordine di attraversamento per verificare la struttura
public void inorderTraversal (nodo nodo) {
if (node! =null) {
InorderTraversal (node.left);
System.out.print (node.data + "");
InorderTraversal (node.right);
}
}
public static void main (string [] args) {
int altezza =2; // 3 livelli (root + 2 Altro)
PerfectBinaryTree PerfectTree =new PerfectBinaryTree (altezza);
System.out.println ("In ordine di attraversamento:");
PerfectTree.InOrderTraversal (PerfectTree.Root); // output:4 2 5 1 6 3 7
}
}
`` `
Spiegazione:
1. `Node` Classe:
* Rappresenta un nodo nell'albero binario.
* Contiene `data` (un numero intero in questo esempio),` sinistra` e `destro '. Puntatori.
2. `PerfectBinaryTree` Classe:
* `root`:il nodo radice dell'albero.
* `Height`:l'altezza dell'albero. La radice è di livello 0, quindi un albero di altezza `h` ha livelli` h+1`.
* `PerfectBinaryTree (int altezza)`:il costruttore. Prende l'altezza desiderata dell'albero binario perfetto come input. Fondamentalmente, chiama `costructPerFectBinaryTree ()` per costruire la struttura dell'albero in modo ricorsivo.
3. `ConstructPerFectBinaryTree (int currentlevel, int maxheight)`:
* Questa è la funzione di supporto ricorsivo che costruisce l'albero.
* `Currentlevel`:il livello corrente in costruzione (a partire da 0 per la radice).
* `Maxheight`:l'altezza massima dell'albero.
* Caso base: `Currentlevel> MaxHeight`:Se il` Currentlevel` supera il `maxheight`, significa che abbiamo raggiunto oltre i nodi foglia, quindi restituiamo` null`.
* Passaggio ricorsivo:
* Crea un nuovo `nodo '. Il valore `data` è impostato (in questo esempio) su` 2^Currentlevel` per dimostrare la struttura basata sul livello, ma questa può essere qualsiasi logica per inizializzare i dati del nodo.
* Chiama ricorsivamente `costructPerFectBinaryTree ()` per costruire i sottostrutimenti sinistra e destra, aumentando `Currentlevel` in ogni chiamata.
* Collega i subtrees appena creati al nodo corrente (`node.left` e` node.right`).
* Restituisce il nodo appena creato.
4. `InorderTraversal (nodo nodo)`:
* Un attraversamento standard per stampare gli elementi dell'albero. Questo è solo per dimostrazione e verifica.
* A sinistra -> root -> a destra
5. `Main` Metodo:
* Dimostra come creare un oggetto `PerfectBinaryTree` con un'altezza specificata.
* Chiama `InorderTraversal` per stampare l'albero.
Considerazioni importanti:
* Costruzione: La chiave per creare un albero binario perfetto è l'approccio di costruzione ricorsivo. Garantisce che tutti i livelli siano completamente riempiti prima di passare a quello successivo.
* Inizializzazione dei dati: L'esempio utilizza `math.pow (2, currentlevel)` per inizializzare i `data` del nodo, ma puoi adattarlo per popolare l'albero con tutti i dati desiderati. La parte essenziale è popolare tutti i nodi ad ogni livello.
* Immutabilità (opzionale): Se si desidera che l'albero sia immutabile dopo la creazione, crea il `nodo` è` data`, `sinistra` e` a destra` campi `final` e non fornire alcun metodo per cambiare la struttura dell'albero dopo la sua costruzione.
* Nessun inserimento/eliminazione (di solito): Poiché gli alberi binari perfetti sono intrinsecamente bilanciati, l'inserimento diretto o la cancellazione dei nodi * pur mantenendo la struttura perfetta * è difficile e spesso poco pratico. Se è necessario inserire/eliminare, in genere dovresti ricostruire completamente l'albero dopo ogni operazione. Gli alberi binari perfetti vengono spesso utilizzati quando il set di dati è noto in anticipo e rimane statico.
* Rappresentazione dell'array: A causa della loro struttura regolare, gli alberi binari perfetti possono essere rappresentati in modo efficiente usando array (specialmente se non è necessario inserire/eliminare elementi). La radice è all'indice 0. Il figlio sinistro del nodo all'indice `i` è a` 2i + 1` e il bambino destro è a `2i + 2`. Ciò evita la necessità di oggetti e puntatori `Node` espliciti, salvando spazio.
Esempio:rappresentazione dell'array di un albero binario perfetto
Un albero binario perfetto può essere immagazzinato in modo molto efficiente in un array. Considera l'albero con altezza 2:
`` `
1
/ \ \
2 3
/ \ / \
4 5 6 7
`` `
La rappresentazione dell'array sarebbe:
`` `
[1, 2, 3, 4, 5, 6, 7]
`` `
Le relazioni tra genitore e bambini sono implicite negli indici dell'array:
* Genitore del nodo all'indice `i` è su indice` (i-1)/2` (divisione integer)
* Lasciato figlio del nodo all'indice `i` è all'indice` 2i + 1`
* Il figlio giusto del nodo all'indice `i` è all'indice` 2i + 2`
Questa rappresentazione di array è incredibilmente efficiente dal punto di vista spazio per gli alberi binari perfetti perché non ci sono lacune nell'array.
Quando usare alberi binari perfetti:
* Quando i dati sono noti in anticipo e rimangono statici.
* Quando hai bisogno di una struttura ad albero equilibrata garantita.
* Quando si dà la priorità all'accesso rapido ai nodi in base alla loro posizione all'interno dell'albero.
* Le strutture di dati HEAP (Min-Heaps, Max-Heaps) sono comunemente implementate utilizzando la rappresentazione dell'array di un albero binario * quasi completo *, che è correlato a un albero binario perfetto.
Gli alberi binari perfetti sono preziosi per casi d'uso specifici in cui la loro struttura rigida e le prestazioni prevedibili offrono vantaggi. Tuttavia, per gli scenari dinamici in cui è spesso necessario inserire o eliminare i nodi, altre strutture di albero bilanciate come alberi AVL o alberi rossi neri sono generalmente più adatti.
Programmazione © www.354353.com