Volledige Binêre Boom vs Volle Binêre Boom
Binêre boom is 'n boom waar elke nodus een of twee kinders het. In 'n binêre boom kan 'n nodus nie meer as twee kinders hê nie. In 'n binêre boom word kinders as "links" en "regs" kinders genoem. Die kind nodusse bevat 'n verwysing na hul ouer. 'n Volledige binêre boom is 'n binêre boom waarin elke vlak van die binêre boom heeltemal gevul is behalwe die laaste vlak. In die ongevulde vlak word die nodusse geheg vanaf die mees linkse posisie. 'n Vol binêre boom is 'n boom waarin elke knoop in die boom twee kinders het behalwe die blare van die boom.
Wat is Volle Binêre Boom?
Volledige binêre boom is 'n binêre boom waarin elke nodus in die boom presies nul of twee kinders het. Met ander woorde, elke knoop in die boom behalwe die blare het presies twee kinders. Figuur 1 hieronder beeld 'n volledige binêre boom uit. In 'n vol binêre boom is die aantal nodusse (n), aantal lae (l) en die aantal interne nodusse (i) op 'n spesiale manier verwant sodat as jy enige een van hulle ken, jy die ander twee kan bepaal waardes soos volg:
1. As 'n volledige binêre boom i interne nodusse het:
– Aantal blare l=i+1
– Totale aantal nodusse n=2i+1
2. As 'n volledige binêre boom n nodusse het:
– Aantal interne nodusse i=(n-1)/2
– Aantal blare l=(n+1)/2
3. As 'n vol binêre boom l blare het:
– Totale aantal nodusse n=2l-1
– Aantal interne nodusse i=l-1
Wat is volledige binêre boom?
Soos getoon in figuur 2, is 'n volledige binêre boom 'n binêre boom waarin elke vlak van die boom heeltemal gevul is behalwe die laaste vlak. Ook, in die laaste vlak, moet nodusse geheg word vanaf die mees linkse posisie. 'n Volledige binêre boom van hoogte h voldoen aan die volgende voorwaardes:
– Vanaf die wortelknoop verteenwoordig die vlak bokant laaste vlak 'n volle binêre boom met hoogte h-1
– Een of meer nodusse op die laaste vlak kan 0 of 1 kinders hê
– As a, b twee nodusse in die vlak bokant die laaste vlak is, dan het a meer kinders as b as en slegs as a links van b geleë is
Wat is die verskil tussen Volledige Binêre Boom en Vol Binêre Boom?
Volledige binêre bome en vol binêre bome het 'n duidelike verskil. Terwyl 'n volledige binêre boom 'n binêre boom is waarin elke nodus nul of twee kinders het, is 'n volledige binêre boom 'n binêre boom waarin elke vlak van die binêre boom heeltemal gevul is behalwe die laaste vlak. Sommige spesiale datastrukture soos hope moet volledige binêre bome wees terwyl dit nie vol binêre bome hoef te wees nie. In 'n volledige binêre boom, as jy die aantal totale nodusse of die aantal lae of die aantal interne nodusse ken, kan jy die ander twee baie maklik vind. Maar 'n volledige binêre boom het nie 'n spesiale eienskap wat hierdie drie eienskappe in verband bring nie.
