Vi vet a träd är en icke-linjär datastruktur. Den har ingen begränsning på antalet barn. AVad är ett komplett binärt träd?

Ett komplett binärt träd är en speciell typ av binärt träd där alla nivåer i trädet fylls helt utom de lägsta nivånoderna som fylls från så vänster som möjligt.

Komplett binärt träd

Lite terminologi för Complete Binary Tree:

• Rot – Nod där ingen kant kommer från föräldern. Exempel -nod A
• Barn – Nod som har någon inkommande kant kallas barn. Exempel – noderna B, F är barn till A respektive C.
• Syskon – Noder som har samma förälder är syskon. Exempel- D, E är syskon eftersom de har samma förälder B.
• Grad av en nod – Antal barn till en viss förälder. Exempel- Graden av A är 2 och graden av C är 1. Graden av D är 0.
• Interna/Externa noder – Lövnoder är externa noder och icke lövnoder är interna noder.
• Nivå – Räkna noder i en väg för att nå en destinationsnod. Exempel- Nivån på nod D är 2 eftersom noderna A och B bildar vägen.
• Höjd – Antal kanter för att nå målnoden, roten är på höjden 0. Exempel – Höjd på nod E är 2 eftersom den har två kanter från roten.

Egenskaper för komplett binärt träd:

• Ett komplett binärt träd sägs vara ett riktigt binärt träd där alla löv har samma djup.
• I ett komplett binärt träd antal noder på djupet d är 2 ^d .
• I ett komplett binärt träd med n nodhöjden på trädet är log(n+1) .
• Alla nivåer förutom den sista nivån är helt fulla.

Perfekt binärt träd kontra komplett binärt träd:

Ett binärt träd med höjden 'h' med det maximala antalet noder är a perfekt binärt träd.
För en given höjd h , är det maximala antalet noder 2 ^h+1 -1 .

A komplett binärt träd med höjd h är ett perfekt binärt träd upp till höjd h-1 , och i den sista nivån lagras element i vänster till höger ordning.

Exempel 1:

Ett binärt träd

Höjden på det givna binära trädet är 2 och det maximala antalet noder i det trädet är n=2^h+1-1 = 2²⁺¹-1 = 2³-1 = 7 .
Därför kan vi dra slutsatsen att det är så ett perfekt binärt träd .
Nu för ett komplett binärt träd, det är fullt upp till höjden h-1 dvs.; 1, och de sista nivåelementen lagras i vänster till höger ordning. Därför är det också ett komplett binärt träd. Här är representationen av element när de lagras i en array

Element lagrat i en array nivå för nivå

I arrayen lagras alla element kontinuerligt.

Exempel 2:

applet

Ett binärt träd

Höjden på det givna binära trädet är 2 och det maximala antalet noder som bör finnas där är 2^h+1– 1 = 2²⁺¹– 1 = 2³– 1 = 7 .
Men antalet noder i trädet är 6 . Därför är det inte ett perfekt binärt träd .
Nu för ett komplett binärt träd, det är fullt upp till höjden h-1 dvs.; 1 , och det sista nivåelementet lagras i vänster till höger ordning. Därför är detta en komplett binärt träd . Lagra elementet i en array och det blir som;

Element lagrat i en array nivå för nivå

Exempel 3:

factorial i java

Ett binärt träd

Höjden på det binära trädet är 2 och det maximala antalet noder som kan finnas där är 7, men det finns bara 5 noder så det är inte ett perfekt binärt träd .
I fallet med ett komplett binärt träd ser vi att på den sista nivån är elementen inte fyllda från vänster till höger ordning. Så är det inte ett fullständigt binärt träd .

Element lagrat i en array nivå för nivå

Elementen i arrayen är inte kontinuerliga.

Fullständigt binärt träd vs komplett binärt träd:

För ett helt binärt träd har varje nod antingen 2 barn eller 0 barn.

Exempel 1:

Ett binärt träd

I det givna binära trädet finns det ingen nod med grad 1, antingen 2 eller 0 barn för varje nod, därför är det ett helt binärt träd .

För ett komplett binärt träd lagras element nivå för nivå och inte från den vänstra sidan på den sista nivån. Därför är detta inte ett fullständigt binärt träd . Arrayrepresentationen är:

Element lagrat i en array nivå för nivå

Exempel 2:

Ett binärt träd

I det givna binära trädet finns det ingen nod med grad 1. Varje nod har en grad på antingen 2 eller 0. Därför är det en fullt binärt träd .

För ett komplett binärt träd lagras element på ett nivå för nivå och fylls från den vänstra sidan av den sista nivån. Därav detta a komplett binärt träd . Nedan är arrayrepresentationen av trädet:

Element lagrat i en array nivå för nivå

Exempel 3:

Ett binärt träd

I det givna binära trädet har noden B grad 1 som bryter mot egenskapen för fullt binärt träd, därför är det inte ett fullständigt binärt träd

mycricketlive

För ett komplett binärt träd lagras element nivå för nivå och fylls från den vänstra sidan av den sista nivån. Därför är detta en komplett binärt träd . Arrayrepresentation av det binära trädet är:

Element lagrat i en array nivå för nivå

Exempel 4:

ett binärt träd

I det givna binära trädet har noden C grad 1 vilket bryter mot egenskapen för ett helt binärt träd, så det är inte ett fullständigt binärt träd

För ett komplett binärt träd lagras element nivå för nivå och fylls från den vänstra sidan av den sista nivån. Här bryter nod E mot villkoret. Därför är detta inte ett fullständigt binärt träd .

Skapande av ett komplett binärt träd:

Vi vet a komplett binärt träd är ett träd där förutom den sista nivån (säg l )alla andra nivåer har ( 2l ) noder och noderna är uppradade från vänster till höger sida.
Det kan representeras med hjälp av en array. Om föräldern är det index i så det vänstra barnet är kl 2i+1 och rätt barn är på 2i+2 .

sträng en int

Komplett binärt träd och dess arrayrepresentation

Algoritm:

För skapandet av en Komplett binärt träd , vi kräver en Steg 1: Initiera roten med en ny nod när trädet är tomt.

Steg 2: Om trädet inte är tomt, skaffa frontelementet

• Om det främre elementet inte har ett vänster underordnat, ställ in det vänstra barnet till en ny nod
• Om rätt barn inte är närvarande ställ in rätt barn som en ny nod

Steg 3: Om noden har båda barnen då pop det från kön.

Steg 4: Ställ den nya datan i kö.

Illustration:

Tänk på följande array:

1. Det första elementet är roten (värde vid index = 0 )

A tas som rot

2. Nästa element (vid index = 1 ) kommer att vara vänster och det tredje elementet (index = 2 ) kommer att vara rätt barn av roten

importera skanner java

B som vänster barn och D som höger barn

3. fjärde (index = 3 ) och femte elementet (index = 4 ) kommer att vara vänster och höger underordnad B-nod

E och F är vänster och höger barn till B

4. Nästa element (index = 5 ) kommer att lämnas som barn till noden D

G görs till vänster under D-noden

Så här skapas ett komplett binärt träd.

Genomförande: För implementering av att bygga ett komplett binärt träd från nivåorderövergång ges in den här posten .

Tillämpning av det kompletta binära trädet:

• Hög sortering
• Högsorteringsbaserad datastruktur

Kontrollera om ett givet binärt träd är komplett eller inte: Följ den här posten för att kontrollera om det givna binära trädet är komplett eller inte.