Nyckelegenskaper för ett perfekt binärt träd
Ett perfekt binärt träd (även kallat ett komplett binärt träd i den meningen att alla nivåer är fulla) uppvisar följande egenskaper:
1. Alla interna noder har exakt två barn: Varje nod som inte är en bladnod måste ha ett vänsterbarn och ett höger barn.
2. Alla bladnoder är på samma nivå: Djupet på alla bladnoder (noder utan barn) är identiskt. Detta betyder att trädet är perfekt balanserat.
3. Antalet noder på nivå `i` är` 2^i`: Där rotnivån betraktas som nivå 0.
4. Det totala antalet noder i ett perfekt binärt träd av höjd `h` är` 2^(H+1) - 1` .
5. Höjden på ett perfekt binärt träd med `n` noder är` log2 (n+1) - 1` . Detta är ofta ungefärligt som `log2 (n)`.
Implikationer av dessa egenskaper:
* Ett perfekt binärt träd är i sig balanserat.
* Dess struktur är mycket förutsägbar och regelbunden.
* Det är mycket utrymmeeffektivt, med minimalt bortkastat minne på grund av ofyllda noder.
Implementeringsdetaljer i Java
Så här kan du implementera ett perfekt binärt träd i Java, med fokus på en grundstruktur och nyckeloperationer:
`` `Java
klass PerfectBinaryTree {
statisk klassnod {
int data;
Nod kvar;
Nod till höger;
Nod (int data) {
this.data =data;
this.left =null;
this.right =null;
}
}
Nodrot;
int höjd; // Höjden på trädet (antal nivåer - 1)
public PerfectBinaryTree (int höjd) {
this.hög =höjd;
this.root =constructperfectBinaryTree (0, höjd);
}
privat nodkonstruktionsperfectBinaryTree (int currentElevel, int maxheight) {
if (currentLevel> maxheight) {
returnera null;
}
// Skapa en nod
Nodnod =ny nod ((int) Math.pow (2, currentElevel)); // Exempel:Använd 2^nivå som nodvärde
// Skapa rekursivt vänster och höger underträd
node.left =constructperfectBinaryTree (currentElevel + 1, MaxHeight);
node.right =constructperfectBinaryTree (currentElevel + 1, MaxHeight);
returnera nod;
}
// Exempel:inorder traversal för att verifiera strukturen
public void inorderTraversal (nodnod) {
if (node! =null) {
inorderTraversal (node.left);
System.out.print (node.data + "");
inorderTraversal (node.right);
}
}
public static void main (String [] args) {
int höjd =2; // 3 nivåer (rot + 2 till)
PerfectBinaryTree PerfecteTree =new PerfectBinaryTree (höjd);
System.out.println ("inorder traversal:");
PerfectTree.InorderTraversal (PerfectTree.root); // utgång:4 2 5 1 6 3 7
}
}
`` `
Förklaring:
1. `node` klass:
* Representerar en nod i det binära trädet.
* Innehåller "data" (ett heltal i det här exemplet), "vänster" och "höger" pekare.
2. `PerfectBinaryTree` klass:
* `Root`:Trädets rotnod.
* `Höjd ':trädets höjd. Roten är nivå 0, så ett höjd av höjd `h` har` h+1 'nivåer.
* `PerfectBinaryTree (int höjd)`:konstruktören. Det tar den önskade "höjden" på det perfekta binära trädet som ingång. Av avgörande betydelse kallar det `constructperfectBinaryTree ()` för att bygga trädstrukturen rekursivt.
3. `ConstructPerFectBinaryTree (int CurrentLevel, int maxHeight)`:
* Detta är den rekursiva hjälpfunktionen som bygger trädet.
* `CURRENTLEVEL`:Den nuvarande nivån som byggs (börjar från 0 för roten).
* `MaxHeight`:Trädets maximala höjd.
* Basfall: `CurrentLevel> MaxHeight ':Om' CurrentLevel 'överskrider" MaxHeight', betyder det att vi har nått utöver bladnoderna, så vi returnerar "noll".
* Rekursivt steg:
* Skapar en ny `nod '. "Data" -värdet är inställt (i det här exemplet) till "2^currentElevel" för att visa den nivåbaserade strukturen, men detta kan vara vilken logik som initierar nodens data.
* Rekursivt ringer `constructperfectBinaryTree ()` för att bygga vänster och högra underträden, vilket ökar "currentLevel" i varje samtal.
* Ansluter de nyligen skapade underträdarna till den aktuella noden (`node.left` och` node.right`).
* Returnerar den nyligen skapade noden.
4. `inOrderTraversal (nodnod)`:
* En standardövervakning för att skriva ut elementen i trädet. Detta är bara för demonstration och verifiering.
* Vänster -> rot -> höger
5. `Main` Metod:
* Demonstrerar hur man skapar ett "PerfectBinaryTree" -objekt med en viss höjd.
* Ringer `inorderTraversal` för att skriva ut trädet.
Viktiga överväganden:
* konstruktion: Nyckeln till att skapa ett perfekt binärt träd är den rekursiva konstruktionsmetoden. Det säkerställer att alla nivåer är helt fyllda innan du flyttar till nästa.
* Datainitiering: Exemplet använder `Math.pow (2, currentElevel)` för att initialisera nodens `data ', men du kan anpassa detta för att fylla trädet med önskad data. Den väsentliga delen är att fylla alla noder på varje nivå.
* Immutability (valfritt): Om du vill att trädet ska vara oföränderligt efter skapandet, gör "node" -data "," vänster "och" höger "-fält" slutgiltiga "och ger inga metoder för att ändra trädets struktur efter att det har byggts.
* ingen insättning/borttagning (vanligtvis): Eftersom perfekta binära träd i sig är balanserade, är direkt införande eller borttagning av noder * samtidigt som den perfekta strukturen * är svårt och ofta opraktiskt. Om du behöver infoga/ta bort måste du vanligtvis rekonstruera trädet efter varje operation. Perfekta binära träd används oftast när datasättet är känt i förväg och förblir statisk.
* Array Representation: På grund av deras vanliga struktur kan perfekta binära träd effektivt representeras med hjälp av matriser (särskilt om du inte behöver infoga/ta bort element). Roten är vid index 0. Nodens vänstra barn vid indexet `i` är på` 2i + 1` och det högra barnet är på `2i + 2`. Detta undviker behovet av uttryckliga "nod" -objekt och pekare, vilket sparar utrymme.
Exempel:Array Representation av ett perfekt binärt träd
Ett perfekt binärt träd kan förvaras mycket effektivt i en matris. Tänk på trädet med höjd 2:
`` `
1
/ \
2 3
/ \ / \
4 5 6 7
`` `
Array -representationen skulle vara:
`` `
[1, 2, 3, 4, 5, 6, 7]
`` `
Förhållandena mellan förälder och barn är implicit i matrisindexen:
* Förälder till nod vid indexet `i 'är på index' (i-1)/2 '(heltal)
* Left Child of Node vid Index `i` är på Index` 2i + 1`
* Höger barn av nod vid index `i` är på index` 2i + 2`
Denna matrisrepresentation är oerhört utrymmeeffektiv för perfekta binära träd eftersom det inte finns några luckor i matrisen.
När man ska använda perfekta binära träd:
* När uppgifterna är kända i förväg och förblir statiska.
* När du behöver en garanterad balanserad trädstruktur.
* När du prioriterar snabb åtkomst till noder baserat på deras position i trädet.
* HEAP-datastrukturer (min-heaps, max-heaps) implementeras vanligtvis med hjälp av matrisrepresentationen av ett * nästan komplett * binärt träd, som är relaterat till ett perfekt binärt träd.
Perfekta binära träd är värdefulla för specifika användningsfall där deras styva struktur och förutsägbara prestanda ger fördelar. För dynamiska scenarier där du ofta behöver infoga eller ta bort noder är andra balanserade trädstrukturer som AVL-träd eller röda svarta träd i allmänhet mer lämpade.
