Verschil tussen volledige binaire structuur en volledige binaire structuur

Volledige binaire boom versus volledige binaire structuur

Binaire boom is een boom waarin 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 "juiste" kinderen. De onderliggende knooppunten bevatten een verwijzing naar hun bovenliggende element. Een volledige binaire boom is een binaire boom waarin elk niveau van de binaire boom volledig is ingevuld, behalve het laatste niveau. In het ongevulde niveau worden de knooppunten gekoppeld 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 volledige binaire structuur?

Volledige binaire boom is een binaire boom waarin elk knooppunt in de boom exact 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 structuur is het aantal knooppunten (n), aantal laves (l) en het aantal interne knooppunten (i) op ​​een speciale manier gerelateerd, zodat als u een van deze kent u de andere twee kunt bepalen waarden als volgt:

1. Als een volledige binaire structuur i interne knooppunten heeft:

- Aantal bladeren l = i + 1

- Totaal aantal knooppunten n = 2 * i + 1

2. Als een volledige binaire boom n nodes heeft:

- Aantal interne knooppunten i = (n-1) / 2

- Aantal bladeren l = (n + 1) / 2

3. Als een volledige binaire boom l heeft verlaten:

- Totaal aantal knooppunten n = 2 * l-1

- Aantal interne knooppunten i = l-1

Wat is Complete Binary Tree?

Zoals weergegeven in figuur 2, is een volledige binaire boom een ​​binaire boom waarin elk niveau van de boom volledig is ingevuld, behalve het laatste niveau. In het laatste niveau moeten ook knooppunten worden gekoppeld vanaf de meest linkse positie. Een volledige binaire boom met hoogte h voldoet aan de volgende voorwaarden:

- Vanaf het basisknooppunt vertegenwoordigt het niveau boven het laatste niveau een volledige binaire boom met hoogte h-1

- Een of meer knooppunten op het laatste niveau kunnen 0 of 1 kinderen bevatten

- Als a, b twee knooppunten in het niveau boven het laatste niveau zijn, dan heeft a meer kinderen dan b als en alleen als a links van b ligt

Wat is het verschil tussen Volledige binaire structuur en Volledige binaire structuur?

Volledige binaire bomen en volledige binaire bomen hebben een duidelijk verschil. Hoewel 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 ingevuld, behalve het laatste niveau. Sommige speciale gegevensstructuren, zoals hopen, moeten volledige binaire bomen zijn, terwijl ze geen volledige binaire bomen hoeven te zijn. In een volledige binaire boom, als je het aantal totale knooppunten of het aantal laves of het aantal interne knooppunten kent, kun je de andere twee heel gemakkelijk vinden. Maar een volledige binaire boom heeft geen speciale eigenschap die betrekking heeft op deze drie attributen.