ROZDIEL MEDZI ÚPLNÝM A ÚPLNÝM BINÁRNYM STROMOM

Binárny strom

Existujú rôzne typy binárnych stromov ale tu budeme diskutovať o rozdieloch Kompletný binárny strom a Úplný binárny strom .

Úplný binárny strom:

Úplný binárny strom je binárny strom, v ktorom všetky uzly majú buď 0 alebo 2 potomkov . Inými slovami, úplný binárny strom je binárny strom, v ktorom všetky uzly, okrem listových, majú dvoch potomkov.

Úplný binárny strom
java for loop

nech, i je počet vnútorných uzlov
n byť celkový počet uzlov
l byť počet listov
l byť počet úrovní

potom

Počet listov je (i + 1) .
Celkový počet uzlov je (2i + 1) .
Počet vnútorných uzlov je (n – 1) / 2 .
Počet listov je (n + 1) / 2 .
Celkový počet uzlov je (2 l – 1) .
Počet vnútorných uzlov je (l – 1) .
Počet listov je najviac (2^l- 1) .

Kompletný binárny strom:

Binárny strom sa nazýva a úplný binárny strom ak všetky jeho úrovne, možno s výnimkou poslednej úrovne, majú maximálny počet možných uzlov a všetky uzly v posledná úroveň sa objaví čo najviac vľavo .

Kompletný binárny strom

Existujú 2 body, ktoré môžete rozpoznať odtiaľto,

Vždy je potrebné najskôr vyplniť ľavú stranu uzla listu.

Nie je potrebné, aby posledný listový uzol mal pravého súrodenca.

Skontrolujte nasledujúce príklady, aby ste lepšie pochopili úplný a úplný binárny strom.

Príklad 1:

Ani úplné, ani plné

Uzol C má teda len jedno dieťa, nie je to úplný binárny strom.

Uzol C má tiež pravé dieťa, ale nemá ľavé dieťa tiež to nie je úplný binárny strom.

Binárny strom zobrazený vyššie je teda ani úplný, ani úplný binárny strom.

Príklad 2:

Plné, ale nie úplné

Všetky uzly majú buď 0 alebo 2 potomstvo teda, je to úplný binárny strom .
Nie je to úplný binárny strom, pretože uzol B nemá žiadne deti, zatiaľ čo node C má deti a podľa úplného binárneho stromu by sa uzly mali vyplniť z ľavá strana .

Binárny strom zobrazený vyššie je teda a Úplný binárny strom a to je nie je úplný binárny strom.

Príklad 3:
znak na reťazec

Kompletné, ale nie plné

Je to úplný binárny strom, pretože všetky uzly zostávajú vyplnené.
Uzol B má teda len jedno dieťa, nie je to úplný binárny strom.

Binárny strom zobrazený vyššie je teda a Kompletný binárny strom a to je nie je úplný binárny strom.

Príklad 4:

Kompletné a plné

Je to a Kompletné binárne strom, pretože všetky uzly sú vľavo vyplnené .

Všetky uzly majú buď 0 alebo 2 potomstvo, preto je a úplný binárny strom .

Binárny strom zobrazený vyššie je teda úplný aj úplný binárny strom.

Áno nie.	Kompletný binárny strom	Úplný binárny strom
1.	V úplnom binárnom strome môže mať uzol na poslednej úrovni iba jedného potomka.	V úplnom binárnom strome nemôže mať uzol iba jedno dieťa.
2.	V úplnom binárnom strome by mal byť uzol vyplnený zľava doprava.	V úplnom binárnom strome neexistuje poradie vypĺňania uzlov.
3.	Kompletné binárne stromy sa používajú hlavne v dátových štruktúrach založených na halde.	Úplný binárny strom ako taký nemá žiadne uplatnenie, ale nazýva sa aj správnym binárnym stromom.
4.	Kompletný binárny strom sa tiež nazýva takmer úplný binárny strom.	Úplný binárny strom nazývaný aj správny binárny strom alebo 2-strom.
5	Kompletný binárny strom musí mať celý listový uzol presne v rovnakej hĺbke.	Úplná úroveň binárnych listov stromu nemusí byť nevyhnutne v rovnakej hĺbke.

TechCodeview