Co je úplný binární strom?
Úplný binární strom lze definovat jako a binární strom ve kterém všechny uzly mají 0 nebo dvě děti. Jinými slovy, úplný binární strom lze definovat jako binární strom, ve kterém mají všechny uzly dva potomky kromě listových uzlů.
Níže uvedený strom je úplný binární strom:
Výše uvedený strom je úplný binární strom, protože všechny uzly kromě listových mají dva potomky.
Úplný teorém binárního stromu:
Považujte binární strom T za neprázdný strom, pak:
- Nechť jsem vnitřní uzly ve stromu a L je listový uzel ve stromu, pak by se počet listových uzlů rovnal:
L = I + 1 - Pokud má T, I počet vnitřních uzlů a N je celkový počet uzlů, pak by se celkový počet uzlů rovnal:
N = 21 + 1 - Pokud T obsahuje 'N' celkový počet uzlů a 'I' je počet interních uzlů, pak by se počet interních uzlů rovnal:
I = (N-l)/2 - Pokud má 'T' celkový počet uzlů 'N' a 'L' je počet listových uzlů, pak by se počet listových uzlů rovnal:
L = (N+l)/2 - Pokud 'T' obsahuje 'L' počet listových uzlů, pak by se celkový počet uzlů rovnal:
N = 2 1 - 1 - Pokud má 'T' počet listových uzlů 'L' a 'I' je počet vnitřních uzlů, pak by se počet vnitřních uzlů rovnal:
I = L - 1
Co je úplný binární strom?
O binárním stromu se říká, že je úplný binární strom, když jsou všechny úrovně zcela vyplněny kromě poslední úrovně, která se plní zleva.
Níže uvedený strom je úplný binární strom:
Úplný binární strom je podobný úplnému binárnímu stromu s výjimkou dvou rozdílů, které jsou uvedeny níže:
- Plnění listového uzlu musí začínat od levé krajní strany.
- Není povinné, že poslední listový uzel musí mít správného sourozence.
Pojďme pochopit výše uvedené body na příkladu:
Zvažte níže uvedený strom:
Výše uvedený strom je úplný binární strom, ale ne úplný binární strom, protože uzel 6 nemá svého pravého sourozence.
Vytvoření kompletního binárního stromu
Předpokládejme, že máme pole 6 prvků zobrazených níže:
Výše uvedené pole obsahuje 6 prvků, tj. 1, 2, 3, 4, 5, 6. Následující kroky je třeba použít k vytvoření kompletního binárního stromu:
Krok 1: Nejprve vybereme první prvek pole, tedy 1, a vytvoříme kořenový uzel stromu. Počet prvků dostupných v první úrovni je 1.
Krok 2: Nyní vybereme druhý a třetí prvek pole. Ponechte druhý prvek a třetí prvek pole jako levý a pravý potomek kořenového uzlu, jak je znázorněno níže:
Jak můžeme vidět výše, počet prvků dostupných ve druhé úrovni je 2.
Krok 3: Nyní vybereme další dva prvky z pole, tj. 4 a 5. Ponechte tyto dva prvky vlevo a vpravo od uzlu 2, jak je znázorněno níže:
Jak můžeme pozorovat výše, uzly 4 a 5 jsou levým a pravým potomkem uzlu 2.
Krok 4: Nyní vybereme poslední prvek pole, tj. 6, a ponecháme jej jako levého potomka uzlu 3, protože víme, že v úplném binárním stromu jsou uzly vyplněny z levé strany, jak je znázorněno níže:
převod řetězce na int java
Jak můžeme pozorovat, druhá úroveň obsahuje 3 prvky.
Pojďme pochopit rozdíly mezi úplným a úplným binárním stromem prostřednictvím obrázků.
- Binární strom, který je zobrazen níže, není ani úplný, ani úplný binární strom. Není to úplný binární strom, protože uzel 3 má pouze jednoho potomka. Také to není úplný binární strom, protože uzly by měly být vyplněny z levé strany, ale uzel 3 má pravého potomka a nemá levého potomka.
- Binární strom, který je zobrazen níže, je úplný binární strom, ale ne úplný binární strom. Je to úplný binární strom, protože všechny uzly mají buď 0 nebo 2 potomky. Není to úplný binární strom, protože uzel 3 nemá žádné potomky, zatímco uzel 2 má své potomky a my víme, že uzly by měly být vyplněny z levé strany v úplném binárním stromu.
- Binární strom, který je zobrazen níže, je úplný binární strom, ale ne úplný binární strom. Je to kompletní binární strom, protože všechny uzly jsou ponechány vyplněné. Nejedná se o úplný binární strom, protože uzel 2 má pouze jednoho potomka.
- Binární strom, který je zobrazen níže, je úplný i úplný binární strom. Je to kompletní binární strom, protože všechny uzly jsou ponechány vyplněné. Je to úplný binární strom, protože všechny uzly mají buď 0 nebo 2 potomky.
