Wat is een volledige binaire boom?
Een volledige binaire boom kan worden gedefinieerd als a binaire boom waarin alle knooppunten 0 of twee kinderen hebben. Met andere woorden, de volledige binaire boom kan worden gedefinieerd als een binaire boom waarin alle knooppunten twee kinderen hebben, behalve de bladknooppunten.
De onderstaande boom is een volledige binaire boom:
De bovenstaande boom is een volledige binaire boom, aangezien alle knooppunten behalve de bladknooppunten twee kinderen hebben.
Volledige binaire boomstelling:
Beschouw een binaire boom T als een niet-lege boom en dan:
- Stel dat I interne knooppunten in een boom zijn en L een bladknooppunt in een boom, dan zou het aantal bladknooppunten gelijk zijn aan:
L=Ik+1 - Als T een I aantal interne knooppunten heeft en N het totale aantal knooppunten is, dan zou het totale aantal knooppunten gelijk zijn aan:
N = 2I + 1 - Als T het totale aantal knooppunten 'N' bevat en 'I' het aantal interne knooppunten is, dan is het aantal interne knooppunten gelijk aan:
ik = (N-1)/2 - Als 'T' het totale aantal knooppunten 'N' heeft, en 'L' een aantal bladknooppunten is, dan zou het aantal bladknooppunten gelijk zijn aan:
L = (N+1)/2 - Als 'T' het aantal 'L'-bladknooppunten bevat, dan is het totale aantal knooppunten gelijk aan:
N = 2L - 1 - Als 'T' het 'L'-aantal bladknooppunten heeft, en 'I' een aantal interne knooppunten is, dan zou het aantal interne knooppunten gelijk zijn aan:
ik = L-1
Wat is een volledige binaire boom?
Er wordt gezegd dat een binaire boom een volledige binaire boom is als alle niveaus volledig gevuld zijn, behalve het laatste niveau, dat vanaf de linkerkant wordt gevuld.
De onderstaande boom is een volledige binaire boom:
De volledige binaire boom is vergelijkbaar met de volledige binaire boom, behalve de twee verschillen die hieronder worden gegeven:
- De vulling van de bladknoop moet vanaf de meest linkse kant beginnen.
- Het is niet verplicht dat het laatste bladknooppunt de juiste broer of zus moet hebben.
Laten we de bovenstaande punten begrijpen aan de hand van een voorbeeld:
Beschouw de onderstaande boom:
De bovenstaande boom is een volledige binaire boom, maar geen volledige binaire boom, aangezien knooppunt 6 niet de juiste broer of zus heeft.
Creatie van een volledige binaire boom
Stel dat we een array van 6 elementen hebben, zoals hieronder weergegeven:
De bovenstaande array bevat 6 elementen, d.w.z. 1, 2, 3, 4, 5, 6. Hieronder volgen de stappen die moeten worden gebruikt om een volledige binaire boom te maken:
Stap 1: Eerst selecteren we het eerste element van de array, d.w.z. 1, en maken we een hoofdknooppunt van de boom. Het aantal beschikbare elementen in het eerste niveau is 1.
Stap 2: Nu selecteren we het tweede en derde element van de array. Houd het tweede element en het derde element van de array respectievelijk als het linker- en rechterkind van het hoofdknooppunt, zoals hieronder weergegeven:
Zoals we hierboven kunnen zien, is het aantal beschikbare elementen op het tweede niveau 2.
Stap 3: Nu zullen we de volgende twee elementen uit de array selecteren, d.w.z. 4 en 5. Houd deze twee elementen links en rechts van knooppunt 2, zoals hieronder weergegeven:
Zoals we hierboven kunnen zien, zijn knooppunten 4 en 5 respectievelijk het linker- en rechterkind van knooppunt 2.
Stap 4: Nu zullen we het laatste element van de array selecteren, d.w.z. 6, en dit als linkerkind van knooppunt 3 behouden, omdat we weten dat in een volledige binaire boom de knooppunten vanaf de linkerkant worden gevuld, zoals hieronder weergegeven:
Zoals we kunnen zien, bevat het tweede niveau 3 elementen.
operators in Python-programmering
Laten we de verschillen tussen de volledige en volledige binaire boom door de afbeeldingen begrijpen.
- De binaire boom die hieronder wordt weergegeven, is noch een volledige, noch een volledige binaire boom. Het is geen volledige binaire boom omdat knooppunt 3 slechts één kind heeft. Het is ook geen volledige binaire boom, aangezien de knooppunten vanaf de linkerkant moeten worden gevuld, maar knooppunt 3 heeft een rechterkind en geen linkerkind.
- De binaire boom, die hieronder wordt weergegeven, is een volledige binaire boom, maar geen volledige binaire boom. Het is een volledige binaire boom omdat alle knooppunten 0 of 2 kinderen hebben. Het is geen volledige binaire boom omdat knooppunt 3 geen kinderen heeft, terwijl knooppunt 2 zijn kinderen heeft en we weten dat de knooppunten in een volledige binaire boom vanaf de linkerkant moeten worden gevuld.
- De binaire boom die hieronder wordt weergegeven, is een volledige binaire boom, maar geen volledige binaire boom. Het is een complete binaire boom omdat alle knooppunten gevuld blijven. Het is geen volledige binaire boom, aangezien knooppunt 2 slechts één kind heeft.
- De binaire boom die hieronder wordt weergegeven, is zowel een volledige als een volledige binaire boom. Het is een complete binaire boom omdat alle knooppunten gevuld blijven. Het is een volledige binaire boom, aangezien alle knooppunten 0 of 2 kinderen hebben.
