Belangrijkste kenmerken van een perfecte binaire boom

Een perfecte binaire boom (ook wel een volledige binaire boom genoemd in de zin dat alle niveaus vol zijn) vertoont de volgende kenmerken:

1. Alle interne knooppunten hebben precies twee kinderen: Elk knooppunt dat geen bladknooppunt is, moet een linkerkind en een rechterkind hebben.

2. Alle leaf-knooppunten bevinden zich op hetzelfde niveau: De diepte van alle bladknopen (knopen zonder kinderen) is identiek. Dit betekent dat de boom perfect in balans is.

3. Het aantal knooppunten op niveau `i` is `2^i`: Waar het rootniveau als niveau 0 wordt beschouwd.

4. Het totale aantal knooppunten in een perfecte binaire boom met hoogte `h` is `2^(h+1) - 1` .

5. De hoogte van een perfecte binaire boom met `n` knooppunten is `log2(n+1) - 1` . Dit wordt vaak benaderd als `log2(n)`.

Implicaties van deze kenmerken:

* Een perfecte binaire boom is inherent in balans.

* De structuur is zeer voorspelbaar en regelmatig.

* Het is zeer ruimtebesparend, met minimale geheugenverspilling als gevolg van niet-gevulde knooppunten.

Implementatiedetails in Java

Hier leest u hoe u een perfecte binaire boom in Java kunt implementeren, met de nadruk op een basisstructuur en sleutelbewerkingen:

```java

klasse PerfectBinaryTree {

statische klasse Knooppunt {

int-gegevens;

Knooppunt links;

Knooppunt rechts;

Knooppunt(int-gegevens) {

deze.data =gegevens;

dit.links =nul;

dit.rechts =nul;

}

}

Knooppuntwortel;

int hoogte; // Hoogte van de boom (aantal niveaus - 1)

openbare PerfectBinaryTree(int hoogte) {

deze.hoogte =hoogte;

this.root =constructPerfectBinaryTree(0, hoogte);

}

private Node constructPerfectBinaryTree (int currentLevel, int maxHeight) {

if (currentLevel> maxHeight) {

retourneer nul;

}

// Maak een knooppunt

Knooppunt knooppunt =new Node((int)Math.pow(2, currentLevel)); // Voorbeeld:gebruik 2^level als knooppuntwaarde

// Maak recursief een linker- en rechtersubboom

node.left =constructPerfectBinaryTree(currentLevel + 1, maxHeight);

node.right =constructPerfectBinaryTree(currentLevel + 1, maxHeight);

retourknooppunt;

}

// Voorbeeld:Inorder Traversal om de structuur te verifiëren

public void inorderTraversal(knooppunt) {

als (knooppunt!=nul) {

inorderTraversal(node.left);

Systeem.uit.print(node.data + " ");

inorderTraversal(node.right);

}

}

public static void main(String[] args) {

int hoogte =2; // 3 niveaus (root + nog 2)

PerfectBinaryTree perfectTree =nieuwe PerfectBinaryTree(hoogte);

System.out.println("In volgorde doorlopen:");

perfectTree.inorderTraversal(perfectTree.root); // Uitgang:4 2 5 1 6 3 7

}

}

```

Uitleg:

1. `Knooppunt`-klasse:

* Vertegenwoordigt een knooppunt in de binaire boom.

* Bevat 'data' (in dit voorbeeld een geheel getal), 'links' en 'rechts' pointers.

2. `PerfectBinaryTree`-klasse:

* `root`:het hoofdknooppunt van de boom.

* `hoogte`:De hoogte van de boom. De wortel is niveau 0, dus een boom met hoogte `h` heeft `h+1` niveaus.

* `PerfectBinaryTree(int height)`:de constructor. Het neemt de gewenste 'hoogte' van de perfecte binaire boom als invoer. Cruciaal is dat het `constructPerfectBinaryTree()` aanroept om de boomstructuur recursief op te bouwen.

3. `constructPerfectBinaryTree(int currentLevel, int maxHeight)`:

* Dit is de recursieve helperfunctie waarmee de boom wordt opgebouwd.

* `currentLevel`:Het huidige niveau dat wordt gebouwd (beginnend vanaf 0 voor de root).

* `maxHeight`:De maximale hoogte van de boom.

* Basisscenario: `currentLevel> maxHeight`:Als `currentLevel` de `maxHeight` overschrijdt, betekent dit dat we voorbij de leaf-knooppunten zijn gekomen, dus retourneren we `null`.

* Recursieve stap:

* Creëert een nieuw `Knooppunt`. De waarde 'data' is (in dit voorbeeld) ingesteld op '2^currentLevel' om de op niveaus gebaseerde structuur te demonstreren, maar dit kan elke logica zijn voor het initialiseren van de gegevens van het knooppunt.

* Roept recursief `constructPerfectBinaryTree()` aan om de linker- en rechtersubboom te bouwen, waarbij `currentLevel` bij elke aanroep wordt verhoogd.

* Verbindt de nieuw aangemaakte subbomen met het huidige knooppunt (`node.left` en `node.right`).

* Geeft het nieuw gemaakte knooppunt terug.

4. `inorderTraversal(knooppunt)`:

* Een standaard inorder-traversal om de elementen van de boom af te drukken. Dit is alleen ter demonstratie en verificatie.

* Links -> Wortel -> Rechts

5. `hoofd`methode:

* Demonstreert hoe u een `PerfectBinaryTree`-object met een opgegeven hoogte kunt maken.

* Roept `inorderTraversal` aan om de boom af te drukken.

Belangrijke overwegingen:

* Constructie: De sleutel tot het creëren van een perfecte binaire boom is de recursieve constructiebenadering. Het zorgt ervoor dat alle niveaus volledig gevuld zijn voordat naar het volgende wordt gegaan.

* Gegevensinitialisatie: Het voorbeeld gebruikt `Math.pow(2, currentLevel)` om de `data` van het knooppunt te initialiseren, maar u kunt dit aanpassen om de boom te vullen met alle gewenste gegevens. Het essentiële onderdeel is om alle knooppunten op elk niveau te vullen.

* Onveranderlijkheid (optioneel): Als je wilt dat de boom na het maken onveranderlijk is, maak dan de velden 'data', 'links' en 'rechts' van het knooppunt 'definitief' en geef geen methoden op om de structuur van de boom te wijzigen nadat deze is gebouwd.

* Geen invoeging/verwijdering (meestal): Omdat perfecte binaire bomen inherent in balans zijn, is het direct invoegen of verwijderen van knooppunten *met behoud van de perfecte structuur* moeilijk en vaak onpraktisch. Als u moet invoegen/verwijderen, moet u de boom doorgaans na elke bewerking volledig reconstrueren. Perfecte binaire bomen worden meestal gebruikt als de dataset vooraf bekend is en statisch blijft.

* Array-weergave: Vanwege hun regelmatige structuur kunnen perfecte binaire bomen efficiënt worden weergegeven met behulp van arrays (vooral als u geen elementen hoeft in te voegen/verwijderen). De wortel bevindt zich op index 0. Het linkerkind van knooppunt op index `i` bevindt zich op `2i + 1` en het rechterkind bevindt zich op `2i + 2`. Dit vermijdt de noodzaak voor expliciete `Node`-objecten en verwijzingen, waardoor ruimte wordt bespaard.

Voorbeeld:arrayweergave van een perfecte binaire boom

Een perfecte binaire boom kan zeer efficiënt in een array worden opgeslagen. Beschouw de boom met hoogte 2:

```

1

/ \

2 3

/ \ / \

4 5 6 7

```

De array-weergave zou zijn:

```

[1, 2, 3, 4, 5, 6, 7]

```

De relaties tussen ouder en kinderen zijn impliciet in de array-indices:

* Ouder van knooppunt bij index `i` bevindt zich op index `(i-1)/2` (deling van gehele getallen)

* Linker kind van knooppunt bij index `i` bevindt zich op index `2i + 1`

* Rechter kind van knooppunt bij index `i` bevindt zich op index `2i + 2`

Deze array-weergave is ongelooflijk ruimte-efficiënt voor perfecte binaire bomen, omdat er geen gaten in de array zitten.

Wanneer gebruik je perfecte binaire bomen:

* Wanneer de gegevens vooraf bekend zijn en statisch blijven.

* Wanneer u een gegarandeerd evenwichtige boomstructuur nodig heeft.

* Wanneer u prioriteit geeft aan snelle toegang tot knooppunten op basis van hun positie binnen de boom.

* Heap-datastructuren (min-heaps, max-heaps) worden gewoonlijk geïmplementeerd met behulp van de array-representatie van een *bijna volledige* binaire boom, die gerelateerd is aan een perfecte binaire boom.

Perfecte binaire bomen zijn waardevol voor specifieke gebruikssituaties waarbij hun stijve structuur en voorspelbare prestaties voordelen bieden. Voor dynamische scenario's waarin u regelmatig knooppunten moet invoegen of verwijderen, zijn andere gebalanceerde boomstructuren zoals AVL-bomen of rood-zwarte bomen over het algemeen geschikter.