A

Ett binärt träd

Det finns olika typer av binära träd men här ska vi diskutera skillnaden mellan Komplett binärt träd och Fullständigt binärt träd .

Fullständigt binärt träd:

Ett helt binärt träd är ett binärt träd där alla noder har antingen 0 eller 2 avkommor . Med andra ord är ett helt binärt träd ett binärt träd där alla noder, utom bladnoderna, har två avkommor.

partiell differentiering i latex

Ett helt binärt träd

det vackraste leendet i världen

Låta, i vara antalet interna noder
n vara det totala antalet noder
l vara antal blad
l vara antal nivåer

Sedan,

Antalet löv är (i + 1) .
Det totala antalet noder är (2i + 1) .
Antalet interna noder är (n – 1) / 2 .
Antalet löv är (n + 1) / 2 .
Det totala antalet noder är (2l – 1) .
Antalet interna noder är (l – 1) .
Antalet löv är som mest (2^l- 1) .

Komplett binärt träd:

Ett binärt träd sägs vara en komplett binärt träd om alla dess nivåer, utom möjligen den sista nivån, har det maximala antalet möjliga noder, och alla noder i sista nivån visas så långt till vänster som möjligt .

Ett komplett binärt träd

Det finns 2 punkter som du kan känna igen härifrån,

1. Den vänstra sidan av bladnoden måste alltid fyllas först.
2. Det är inte nödvändigt för den sista lövnoden att ha ett rätt syskon.

Kontrollera följande exempel för att förstå det fullständiga och fullständiga binära trädet på ett bättre sätt.

array i java-metoder

Exempel 1:

Varken komplett eller full

• Nod C har därför bara ett barn, det är inte ett fullständigt binärt träd.
• Nod C har också ett högerbarn men inget vänsterbarn alltså det är inte heller ett komplett binärt träd.

Därför är det binära trädet som visas ovan varken fullständigt eller fullständigt binärt träd.

Exempel 2:

python ny linje

Full men inte komplett

• Alla noder har antingen 0 eller 2 avkomma alltså, det är ett fullständigt binärt träd .
Det är inte ett komplett binärt träd eftersom noden B har inga barn medan nod C har barn, och enligt ett komplett binärt träd ska noder fyllas från vänster sida .

Därför är det binära trädet som visas ovan a Fullständigt binärt träd och det är inte ett komplett binärt träd.

Exempel 3:

Komplett men inte full

Det är ett komplett binärt träd eftersom alla noder lämnas fyllda.
• Nod B har bara ett barn, därför det är inte ett fullständigt binärt träd.

Därför är det binära trädet som visas ovan a Komplett binärt träd och det är inte ett fullständigt binärt träd.

Exempel 4:

Komplett och full

if-else uttalande java

• Det är en Komplett binär träd eftersom alla noder är vänster fylld .
• Alla noder har antingen 0 eller 2 avkomma, därför är det en fullt binärt träd .

Därför är det binära trädet som visas ovan både ett komplett och ett fullständigt binärt träd.