Známe a strom je nelineární datová struktura. Nemá žádné omezení na počet dětí. ACo je úplný binární strom?
Úplný binární strom je speciálním typem binárního stromu, kde jsou všechny úrovně stromu zcela vyplněny kromě uzlů nejnižší úrovně, které se vyplňují co nejvíce zleva.
Kompletní binární strom
Některá terminologie kompletního binárního stromu:
- Vykořenit – Uzel, ve kterém žádná hrana nepřichází z rodiče. Příklad -uzel A
- Dítě – Uzel s nějakou příchozí hranou se nazývá potomek. Příklad – uzly B, F jsou potomky A a C.
- Sourozenec – Uzly, které mají stejného rodiče, jsou sourozenci. Příklad - D, E jsou sourozenci, protože mají stejného rodiče B.
- Stupeň uzlu – Počet dětí konkrétního rodiče. Příklad – Stupeň A je 2 a Stupeň C je 1. Stupeň D je 0.
- Interní/Externí uzly – Listové uzly jsou vnější uzly a nelistové uzly jsou vnitřní uzly.
- Úroveň – Počítejte uzly na cestě k dosažení cílového uzlu. Příklad- Úroveň uzlu D je 2, protože uzly A a B tvoří cestu.
- Výška – Počet hran, které mají dosáhnout cílového uzlu, Kořen je ve výšce 0. Příklad – Výška uzlu E je 2, protože má dvě hrany od kořene.
Vlastnosti kompletního binárního stromu:
- O úplném binárním stromu se říká, že je správným binárním stromem, kde všechny listy mají stejnou hloubku.
- V kompletním binárním stromu počet uzlů v hloubce d je 2 d .
- V kompletním binárním stromu s n uzly výška stromu je log(n+1) .
- Všechny úrovně kromě poslední úrovně jsou zcela plné.
Perfektní binární strom vs Kompletní binární strom:
Binární strom výšky „h“ s maximálním počtem uzlů je a perfektní binární strom.
Pro danou výšku h , maximální počet uzlů je 2 h+1 -1 .
A kompletní binární strom výšky h je dokonalý binární strom do výšky h-1 a v prvku poslední úrovně jsou uloženy v pořadí zleva doprava.
Příklad 1:
Binární strom
Výška daného binárního stromu je 2 a maximální počet uzlů v tomto stromu je n=2h+1-1 = 22+1-1 = 23-1 = 7 .
Můžeme tedy dojít k závěru, že ano dokonalý binární strom .
Nyní pro úplný binární strom, je plný až do výšky h-1 tj.; 1 a prvky poslední úrovně jsou uloženy v pořadí zleva doprava. Jedná se tedy také o kompletní binární strom. Zde je znázornění prvků při uložení v poli
Prvek uložený v poli úroveň po úrovni
V poli jsou všechny prvky uloženy nepřetržitě.
Příklad 2:
java iterátor pro mapu
Binární strom
Výška daného binárního stromu je 2 a maximální počet uzlů, které tam mají být, jsou 2h+1– 1 = 22+1– 1 = 23– 1 = 7 .
Ale počet uzlů ve stromu je 6 . Proto je není dokonalý binární strom .
Nyní pro úplný binární strom, je plný až do výšky h-1 tj.; 1 a poslední prvek úrovně jsou uloženy v pořadí zleva doprava. Toto je tedy a kompletní binární strom . Uložte prvek do pole a bude to jako;
Prvek uložený v poli úroveň po úrovni
Příklad 3:
1 milion v číslicích
Binární strom
Výška binárního stromu je 2 a maximální počet uzlů, které tam mohou být, je 7, ale uzlů je pouze 5, takže je není dokonalý binární strom .
V případě úplného binárního stromu vidíme, že v poslední úrovni se prvky nevyplňují zleva doprava. Takže to je není úplný binární strom .
Prvek uložený v poli úroveň po úrovni
Prvky v poli nejsou spojité.
Úplný binární strom vs úplný binární strom:
Pro úplný binární strom má každý uzel buď 2 potomky, nebo 0 potomků.
Příklad 1:
Binární strom
V daném binárním stromě není žádný uzel se stupněm 1, buď 2 nebo 0 potomků pro každý uzel, proto je úplný binární strom .
Pro úplný binární strom jsou prvky uloženy v úrovni po úrovni a nikoli z levé strany v poslední úrovni. Proto je toto není úplný binární strom . Reprezentace pole je:
Prvek uložený v poli úroveň po úrovni
Příklad 2:
Binární strom
V daném binárním stromě není žádný uzel se stupněm 1. Každý uzel má stupeň buď 2 nebo 0. Jedná se tedy o úplný binární strom .
Pro úplný binární strom jsou prvky ukládány způsobem po úrovních a vyplňují se z levé strany poslední úrovně. Proto toto a kompletní binární strom . Níže je znázornění pole stromu:
Prvek uložený v poli úroveň po úrovni
Příklad 3:
Binární strom
V daném binárním stromu má uzel B stupeň 1, který porušuje vlastnost plného binárního stromu, proto je není úplný binární strom
operátor java
Pro úplný binární strom jsou prvky ukládány způsobem podle úrovní a vyplňují se z levé strany poslední úrovně. Toto je tedy a kompletní binární strom . Pole reprezentace binárního stromu je:
Prvek uložený v poli úroveň po úrovni
Příklad 4:
binární strom
V daném binárním stromu má uzel C stupeň 1, který porušuje vlastnost plného binárního stromu, proto je není úplný binární strom
Pro úplný binární strom jsou prvky ukládány způsobem podle úrovní a vyplňují se z levé strany poslední úrovně. Zde uzel E porušuje podmínku. Proto je toto není úplný binární strom .
Vytvoření kompletního binárního stromu:
Známe a kompletní binární strom je strom, ve kterém kromě poslední úrovně (řekněme l )všechny ostatní úrovně mají ( 2l ) uzly a uzly jsou seřazeny zleva doprava.
Může být reprezentován pomocí pole. Pokud je rodič, je to index i takže levé dítě je na 2i+1 a správné dítě je na 2i+2 .
Kompletní binární strom a jeho reprezentace pole
Algoritmus:
abeceda čísel
Pro vytvoření a Kompletní binární strom , požadujeme a Krok 1: Inicializujte kořen s novým uzlem, když je strom prázdný.
Krok 2: Pokud strom není prázdný, získejte přední prvek
- Pokud přední prvek nemá levého potomka, nastavte levého potomka na nový uzel
- Pokud není přítomen správný potomek, nastavte správného potomka jako nový uzel
Krok 3: Pokud má uzel obě děti, pak pop to z fronty.
Krok 4: Zařaďte nová data do fronty.
Ilustrace:
Zvažte níže uvedené pole:
1. 1. prvek bude kořen (hodnota na index = 0 )
A se bere jako kořen
2. Další prvek (na index = 1 ) bude ponechán a třetí prvek (index = 2 ) bude správným potomkem roota
B jako levé dítě a D jako pravé dítě
3. čtvrtý (index = 3 ) a pátý prvek (index = 4 ) bude levým a pravým potomkem uzlu B
zmije plnáE a F jsou levé a pravé dítě B
4. Další prvek (index = 5 ) zůstane potomkem uzlu D
G je levým potomkem uzlu D
Takto je vytvořen kompletní binární strom.
Implementace: Pro implementaci sestavení kompletního binárního stromu je uvedeno procházení pořadím úrovně tento příspěvek .
Aplikace kompletního binárního stromu:
- Řazení haldy
- Struktura dat založená na řazení haldy
Zkontrolujte, zda je daný binární strom úplný nebo ne: Následovat tento příspěvek zkontrolovat, zda je daný binární strom úplný nebo ne.