ROZDÍL MEZI ÚPLNÝM A ÚPLNÝM BINÁRNÍM STROMEM

Binární strom

Existují různé typy binárních stromů ale zde budeme diskutovat o rozdílu Kompletní binární strom a Úplný binární strom .

Úplný binární strom:

Úplný binární strom je binární strom, ve kterém všechny uzly mají buď 0 nebo 2 potomky . Jinými slovy, úplný binární strom je binární strom, ve kterém všechny uzly, kromě listových, mají dva potomky.

hovínko

Úplný binární strom
rajesh khanna

Nechat, i být počet vnitřních uzlů
n být celkový počet uzlů
l být počet listů
l být počet úrovní

Pak,

Počet listů je (i + 1) .
Celkový počet uzlů je (2i + 1) .
Počet vnitřních uzlů je (n – 1) / 2 .
Počet listů je (n + 1) / 2 .
Celkový počet uzlů je (2l – 1) .
Počet vnitřních uzlů je (l – 1) .
Počet listů je maximálně (2^l- 1) .

Kompletní binární strom:

Binární strom se nazývá a kompletní binární strom pokud všechny jeho úrovně, možná kromě poslední úrovně, mají maximální počet možných uzlů a všechny uzly v poslední úroveň se objeví co nejvíce vlevo .

Kompletní binární strom

Zde jsou 2 body, které můžete rozpoznat,

Jako první musí být vždy vyplněna krajní levá strana uzlu listu.

Není nutné, aby poslední listový uzel měl pravého sourozence.

Podívejte se na následující příklady, abyste lépe porozuměli úplnému a úplnému binárnímu stromu.

jak vrátit pole v Javě

Příklad 1:

Ani úplný, ani plný

Uzel C má tedy jen jedno dítě, není to úplný binární strom.

Uzel C má také pravé dítě, ale žádné levé dítě také to není úplný binární strom.

Výše uvedený binární strom tedy je ani úplný, ani úplný binární strom.

Příklad 2:
zip v linuxu

Plný, ale ne úplný

Všechny uzly mají buď 0 nebo 2 potomek tedy, je to úplný binární strom .
Není to úplný binární strom, protože uzel B nemá žádné děti, zatímco uzel C má děti a podle úplného binárního stromu by měly být uzly vyplněny z levá strana .

Binární strom zobrazený výše je tedy a Úplný binární strom a to je není úplný binární strom.

Příklad 3:

Kompletní, ale ne plné

Je to kompletní binární strom, protože všechny uzly jsou ponechány vyplněné.
Uzel B má tedy pouze jedno dítě, není to úplný binární strom.

Binární strom zobrazený výše je tedy a Kompletní binární strom a to je není úplný binární strom.

Příklad 4:

Kompletní a plné
bajtové pole na řetězec java

Je to a Kompletní binární strom, protože všechny uzly jsou vlevo vyplněno .

Všechny uzly mají buď 0 nebo 2 potomek, proto je a úplný binární strom .

Výše uvedený binární strom tedy je úplný i úplný binární strom.

Ano ne.	Kompletní binární strom	Úplný binární strom
1.	V úplném binárním stromu může mít uzel na poslední úrovni pouze jednoho potomka.	V úplném binárním stromu nemůže mít uzel pouze jednoho potomka.
2.	V úplném binárním stromu by měl být uzel vyplněn zleva doprava.	V úplném binárním stromu neexistuje žádné pořadí plnění uzlů.
3.	Kompletní binární stromy se používají hlavně v datových strukturách založených na haldě.	Úplný binární strom jako takový nemá žádnou aplikaci, ale nazývá se také správným binárním stromem.
4.	Kompletní binární strom se také nazývá téměř úplný binární strom.	Úplný binární strom také nazývaný správný binární strom nebo 2-strom.
5	Kompletní binární strom musí mít celý uzel listů v přesně stejné hloubce.	V plné binární úrovni listů stromu nemusí být nutně ve stejné hloubce.

TechCodeview