Voltooi binaire boom versus volledige binaire boom
Binaire boom is een boom waarbij elk knooppunt een of twee kinderen heeft. In een binaire structuur kan een knooppunt niet meer dan twee kinderen hebben. In een binaire boom worden kinderen genoemd als "linker" en "rechter" kinderen. De onderliggende knooppunten bevatten een verwijzing naar hun ouder. Een complete binaire boom is een binaire boom waarin elk niveau van de binaire boom volledig is gevuld behalve het laatste niveau. In het niet-gevulde niveau worden de knooppunten bevestigd vanaf de meest linkse positie. Een volledige binaire boom is een boom waarin elk knooppunt 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, elk knooppunt in de boom behalve de bladeren heeft precies twee kinderen. Afbeelding 1 hieronder toont een volledige binaire boom. In een volledig binaire boom zijn het aantal knooppunten (n), het aantal laves (l) en het aantal interne knooppunten (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 vleugels l = i + 1
- Totaal aantal knooppunten n = 2 * i + 1
2. Als een volledige binaire boom n knooppunten heeft:
- Aantal interne knooppunten i = (n-1) / 2
- Aantal vleugels l = (n + 1) / 2
3. Als een volledige binaire boom l bladeren heeft:
- Totaal aantal knooppunten n = 2 * l-1
- Aantal interne knooppunten i = l-1
Wat is een complete binaire boom?
Zoals getoond in figuur 2, is een complete 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 complete binaire boom met hoogte h voldoet aan de volgende voorwaarden:
- Vanaf het hoofdknooppunt 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 knooppunten 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 Complete Binary Tree en Full Binary Tree?
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 volledig binaire boom het totale aantal knooppunten of het aantal laven of het aantal interne knooppunten kent, kunt u de andere twee heel gemakkelijk vinden. Maar een complete binaire boom heeft geen speciale eigenschap die betrekking heeft op deze drie attributen.
