Volledige binaire boom versus volledige binaire boom
Binaire boom is een boom waarbij elk knooppunt een of twee kinderen heeft. In een binaire boom kan een knoop niet meer dan twee kinderen hebben. In een binaire boom worden kinderen genoemd als "links" en "rechts" kinderen. De onderliggende knooppunten bevatten een verwijzing naar hun bovenliggende knooppunten. Een complete binaire boom is een binaire boom waarin elk niveau van de binaire boom volledig is gevuld, behalve het laatste niveau. In het ongevulde niveau worden de knooppunten bevestigd vanaf de meest linkse positie. Een volledige binaire boom is een boom waarin elke knoop in de boom twee kinderen heeft, behalve de bladeren van de boom.
Wat is een volledige binaire boom?
Volledige binaire boom is een binaire boom waarin elk knooppunt in de boom precies nul of twee kinderen heeft. Met andere woorden, elke knoop in de boom behalve de bladeren heeft precies twee kinderen. Afbeelding 1 hieronder toont een volledige binaire boom. In een volledige binaire boom is het aantal knopen (n), het aantal laves (l) en het aantal interne knopen (i) op een speciale manier gerelateerd, zodat als je er een kent, je de andere twee kunt bepalen waarden als volgt:
1. Als een volledige binaire boom i interne knooppunten heeft:
– Aantal bladeren l=i+1
– Totaal aantal knooppunten n=2i+1
2. Als een volledige binaire boom n knooppunten heeft:
– Aantal interne knooppunten i=(n-1)/2
– Aantal bladeren l=(n+1)/2
3. Als een volledige binaire boom l-bladeren heeft:
– Totaal aantal knooppunten n=2l-1
– Aantal interne knooppunten i=l-1
Wat is een complete binaire boom?
Zoals weergegeven in figuur 2, is een volledige binaire boom een binaire boom waarin elk niveau van de boom volledig is gevuld, behalve het laatste niveau. Ook moeten in het laatste niveau knooppunten worden bevestigd vanaf de meest linkse positie. Een volledige binaire boom met hoogte h voldoet aan de volgende voorwaarden:
– Vanaf het wortelknooppunt vertegenwoordigt het niveau boven het laatste niveau een volledige binaire boom met hoogte h-1
– Een of meer knooppunten in het laatste niveau kunnen 0 of 1 kinderen hebben
– Als a, b twee knopen zijn in het niveau boven het laatste niveau, dan heeft a meer kinderen dan b als en slechts als a links van b ligt
Wat is het verschil tussen een volledige binaire boom en een volledige binaire boom?
Volledige binaire bomen en volledige binaire bomen hebben een duidelijk verschil. Terwijl een volledige binaire boom een binaire boom is waarin elk knooppunt nul of twee kinderen heeft, is een volledige binaire boom een binaire boom waarin elk niveau van de binaire boom volledig is gevuld, behalve het laatste niveau. Sommige speciale datastructuren zoals hopen moeten volledige binaire bomen zijn, terwijl ze geen volledige binaire bomen hoeven te zijn. Als u in een volledige binaire boom het aantal totale knooppunten of het aantal laves of het aantal interne knooppunten kent, kunt u de andere twee heel gemakkelijk vinden. Maar een complete binaire boom heeft geen speciale eigenschap met betrekking tot deze drie attributen.
