Vad är ett fullständigt binärt träd?

Ett helt binärt träd kan definieras som ett binärt träd där alla noder har 0 eller två barn. Med andra ord kan det fullständiga binära trädet definieras som ett binärt träd där alla noder har två barn utom lövnoderna.

Nedanstående träd är ett fullständigt binärt träd:

Ovanstående träd är ett helt binärt träd eftersom alla noder utom lövnoderna har två barn.

Fullständig binär trädsats:

Betrakta ett binärt träd T som ett icke-tomt träd då:

• Låt jag vara interna noder i ett träd och L vara en lövnod i ett träd, då skulle antalet lövnoder vara lika med:
  L = I + 1
• Om T har I antal interna noder och N är det totala antalet noder, då skulle det totala antalet noder vara lika med:
  N = 2I + 1
• Om T innehåller 'N' totalt antal noder och 'I' för att vara antalet interna noder, då skulle antalet interna noder vara lika med:
  I = (N-1)/2
• Om 'T' har 'N' totalt antal noder, och 'L' är ett antal bladnoder, så skulle antalet bladnoder vara lika med:
  L = (N+1)/2
• Om 'T' innehåller 'L' antal lövnoder, skulle det totala antalet noder vara lika med:
  N = 2L - 1
• Om 'T' har 'L' antal lövnoder och 'I' för att vara ett antal interna noder, skulle antalet interna noder vara lika med:
  I = L - 1

Vad är ett komplett binärt träd?

Ett binärt träd sägs vara ett komplett binärt träd när alla nivåer är helt fyllda utom den sista nivån, som är fylld från vänster.

Nedanstående träd är ett komplett binärt träd:

Det fullständiga binära trädet liknar det fullständiga binära trädet förutom de två skillnaderna som anges nedan:

• Fyllningen av bladnoden måste börja från den vänstra sidan.
• Det är inte obligatoriskt att den sista lövnoden måste ha rätt syskon.

Låt oss förstå punkterna ovan genom ett exempel:

Tänk på trädet nedan:

Ovanstående träd är ett komplett binärt träd, men inte ett fullständigt binärt träd eftersom nod 6 inte har sitt rätta syskon.

Skapande av ett komplett binärt träd

Anta att vi har en matris med 6 element som visas enligt nedan:

Ovanstående array innehåller 6 element, dvs 1, 2, 3, 4, 5, 6. Följande är stegen som ska användas för att skapa ett komplett binärt träd:

Steg 1: Först väljer vi det första elementet i arrayen, d.v.s. 1, och gör en rotnod för trädet. Antalet tillgängliga element i den första nivån är 1.

Steg 2: Nu kommer vi att välja det andra och tredje elementet i arrayen. Behåll det andra elementet och det tredje elementet i arrayen som vänster och höger underordnat av rotnoden respektive visas enligt nedan:

Som vi kan observera ovan är antalet tillgängliga element i den andra nivån 2.

Steg 3: Nu kommer vi att välja de nästa två elementen från arrayen, d.v.s. 4 och 5. Behåll dessa två element till vänster och höger om nod 2 som visas nedan:

Som vi kan observera ovan är noderna 4 och 5 det vänstra och högra barnet till nod 2 respektive.

java jämför strängar

Steg 4: Nu kommer vi att välja det sista elementet i arrayen, d.v.s. 6, och behålla det som vänster underordnat av nod 3 eftersom vi vet att i ett komplett binärt träd fylls noderna från vänster sida som visas enligt nedan:

Som vi kan observera att den andra nivån innehåller 3 element.

Låt oss förstå skillnaderna mellan kompletta och fullständiga binära träd genom bilderna.

1. Det binära trädet som visas nedan är varken ett fullständigt eller ett fullständigt binärt träd. Det är inte ett fullständigt binärt träd eftersom nod 3 bara har ett barn. Det är inte heller ett komplett binärt träd då noderna ska fyllas från vänster sida, men nod 3 har ett höger underordnat och inte ett vänster underordnat.
   
2. Det binära trädet, som visas nedan, är ett fullständigt binärt träd men inte ett fullständigt binärt träd. Det är ett helt binärt träd eftersom alla noder har antingen 0 eller 2 barn. Det är inte ett komplett binärt träd eftersom nod 3 inte har några barn medan nod 2 har sina barn och vi vet att noderna ska fyllas från vänster sida i ett komplett binärt träd.
   
3. Det binära trädet som visas nedan är ett komplett binärt träd men inte ett fullständigt binärt träd. Det är ett komplett binärt träd eftersom alla noder lämnas fyllda. Det är inte ett fullständigt binärt träd eftersom nod 2 bara har ett barn.
   
4. Det binära trädet som visas nedan är ett komplett såväl som ett fullständigt binärt träd. Det är ett komplett binärt träd eftersom alla noder lämnas fyllda. Det är ett helt binärt träd eftersom alla noder har antingen 0 eller 2 barn.