TechCodeview

Binární strom znamená, že uzel může mít maximálně dva potomky. Zde binární název sám o sobě naznačuje, že 'dva'; proto může mít každý uzel buď 0, 1 nebo 2 potomky.

Pojďme pochopit binární strom na příkladu.

Výše uvedený strom je binární, protože každý uzel obsahuje maximálně dva potomky. Logická reprezentace výše uvedeného stromu je uvedena níže:

Ve výše uvedeném stromu obsahuje uzel 1 dva ukazatele, tj. levý a pravý ukazatel ukazující na levý a pravý uzel. Uzel 2 obsahuje oba uzly (levý a pravý uzel); proto má dva ukazatele (levý a pravý). Uzly 3, 5 a 6 jsou uzly listové, takže všechny tyto uzly obsahují NULA ukazatel na levé i pravé části.

Vlastnosti binárního stromu

• Na každé úrovni i je maximální počet uzlů 2ⁱ.
• Výška stromu je definována jako nejdelší cesta od kořenového uzlu k listovému uzlu. Strom, který je zobrazen výše, má výšku rovnou 3. Maximální počet uzlů ve výšce 3 je tedy roven (1+2+4+8) = 15. Obecně platí, že maximální možný počet uzlů ve výšce h je (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Minimální možný počet uzlů ve výšce h je roven h+1 .
• Pokud je počet uzlů minimální, pak by výška stromu byla maximální. Naopak, pokud je počet uzlů maximální, pak by výška stromu byla minimální.

Pokud je v binárním stromu počet uzlů 'n'.

Minimální výšku lze vypočítat takto:

Jak víme,

n = 2^h+1-1

n+1 = 2^h+1

Vezmeme poleno na obě strany,

log₂(n+1) = log2(2^h+1)

log₂(n+1) = h+1

h = log₂(n+1) - 1

Maximální výšku lze vypočítat takto:

Jak víme,

n = h+1

h = n-1

Typy binárních stromů

Existují čtyři typy binárních stromů:

Úplný/ správný/ přísný binární strom Kompletní binární strom Perfektní binární strom Degenerovaný binární strom Vyvážený binární strom

1. Úplný/ správný/ přísný binární strom

Úplný binární strom je také známý jako přísný binární strom. Strom lze považovat za úplný binární strom pouze tehdy, pokud každý uzel musí obsahovat 0 nebo 2 potomky. Úplný binární strom lze také definovat jako strom, ve kterém musí každý uzel obsahovat 2 potomky kromě listových uzlů.

Podívejme se na jednoduchý příklad plného binárního stromu.

Ve výše uvedeném stromě můžeme pozorovat, že každý uzel obsahuje nula nebo dva potomky; jedná se tedy o úplný binární strom.

Vlastnosti plného binárního stromu

• Počet listových uzlů se rovná počtu vnitřních uzlů plus 1. Ve výše uvedeném příkladu je počet vnitřních uzlů 5; proto je počet listových uzlů roven 6.
• Maximální počet uzlů je stejný jako počet uzlů v binárním stromu, tedy 2^h+1-1.
• Minimální počet uzlů v úplném binárním stromu je 2*h-1.
• Minimální výška plného binárního stromu je log₂(n+1) - 1.
• Maximální výšku celého binárního stromu lze vypočítat jako:

n = 2*h - 1

Hodně štěstí

n+l = 2*h

globální proměnná javascript

h = n+1/2

Kompletní binární strom

Kompletní binární strom je strom, ve kterém jsou všechny uzly zcela vyplněny kromě poslední úrovně. V poslední úrovni musí být všechny uzly co nejvíce ponechány. V úplném binárním stromu by měly být uzly přidány zleva.

Vytvořme kompletní binární strom.

Výše uvedený strom je úplný binární strom, protože všechny uzly jsou zcela vyplněny a všechny uzly v poslední úrovni jsou přidány vlevo jako první.

Vlastnosti kompletního binárního stromu

• Maximální počet uzlů v úplném binárním stromu jsou 2^h+1- 1.
• Minimální počet uzlů v úplném binárním stromu jsou 2^h.
• Minimální výška kompletního binárního stromu je log₂(n+1) - 1.
• Maximální výška kompletního binárního stromu je

Perfektní binární strom

Strom je dokonalý binární strom, pokud všechny vnitřní uzly mají 2 potomky a všechny listové uzly jsou na stejné úrovni.

Podívejme se na jednoduchý příklad dokonalého binárního stromu.

Níže uvedený strom není dokonalý binární strom, protože všechny listové uzly nejsou na stejné úrovni.

Poznámka: Všechny dokonalé binární stromy jsou úplné binární stromy i úplný binární strom, ale naopak to neplatí, tj. všechny úplné binární stromy a úplné binární stromy jsou dokonalé binární stromy.

Degenerovaný binární strom

Degenerovaný binární strom je strom, ve kterém mají všechny vnitřní uzly pouze jednoho potomka.

Pojďme pochopit zdegenerovaný binární strom prostřednictvím příkladů.

Výše uvedený strom je zdegenerovaný binární strom, protože všechny uzly mají pouze jednoho potomka. Je také známý jako pravoúhlý strom, protože všechny uzly mají pouze pravé potomky.

Výše uvedený strom je také zdegenerovaný binární strom, protože všechny uzly mají pouze jednoho potomka. Je také známý jako strom se zkosením doleva, protože všechny uzly mají pouze levé potomky.

Vyvážený binární strom

Vyvážený binární strom je strom, ve kterém se levý a pravý strom liší nejvýše o 1. Např. AVL a Červeno-černé stromy jsou vyvážené binární stromy.

Pojďme pochopit vyvážený binární strom pomocí příkladů.

Výše uvedený strom je vyvážený binární strom, protože rozdíl mezi levým a pravým podstromem je nulový.

Výše uvedený strom není vyváženým binárním stromem, protože rozdíl mezi levým a pravým podstromem je větší než 1.

Implementace binárního stromu

Binární strom je implementován pomocí ukazatelů. První uzel ve stromu je reprezentován kořenovým ukazatelem. Každý uzel ve stromu se skládá ze tří částí, tj. dat, levého ukazatele a pravého ukazatele. Abychom vytvořili binární strom, musíme nejprve vytvořit uzel. Vytvoříme uživatelsky definovaný uzel, jak je znázorněno níže:

 struct node { int data, struct node *left, *right; } 

Ve výše uvedené struktuře data je hodnota, levý ukazatel obsahuje adresu levého uzlu a pravý ukazatel obsahuje adresu pravého uzlu.

Program binárního stromu v C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Výše uvedený kód volá funkci create() rekurzivně a vytváří nový uzel při každém rekurzivním volání. Když jsou vytvořeny všechny uzly, tvoří binární stromovou strukturu. Proces návštěvy uzlů je známý jako procházení stromem. K návštěvě uzlu se používají tři typy průchodů:

• Průjezd nepořádku
• Přechod předobjednávky
• Předání poštovní poukázky