Binárny strom znamená, že uzol môže mať maximálne dve deti. Tu už samotný binárny názov naznačuje, že „dva“; preto môže mať každý uzol buď 0, 1 alebo 2 deti.

Poďme pochopiť binárny strom prostredníctvom príkladu.

Vyššie uvedený strom je binárny strom, pretože každý uzol obsahuje maximálne dve deti. Logická reprezentácia vyššie uvedeného stromu je uvedená nižšie:

Vo vyššie uvedenom strome obsahuje uzol 1 dva ukazovatele, t. j. ľavý a pravý ukazovateľ ukazujúci na ľavý a pravý uzol. Uzol 2 obsahuje oba uzly (ľavý aj pravý uzol); preto má dva ukazovatele (ľavý a pravý). Uzly 3, 5 a 6 sú listové uzly, takže všetky tieto uzly obsahujú NULOVÝ ukazovateľ na ľavej aj pravej časti.

Vlastnosti binárneho stromu

• Na každej úrovni i je maximálny počet uzlov 2ⁱ.
• Výška stromu je definovaná ako najdlhšia cesta od koreňového uzla po listový uzol. Strom, ktorý je zobrazený vyššie, má výšku rovnajúcu sa 3. Preto sa maximálny počet uzlov vo výške 3 rovná (1+2+4+8) = 15. Vo všeobecnosti je maximálny možný počet uzlov vo výške h je (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Minimálny možný počet uzlov vo výške h sa rovná h+1 .
• Ak je počet uzlov minimálny, výška stromu by bola maximálna. Naopak, ak je počet uzlov maximálny, potom by výška stromu bola minimálna.

Ak je v binárnom strome počet uzlov 'n'.

Minimálnu výšku možno vypočítať takto:

Ako vieme,

vyhľadávanie bfs

n = 2^h+1-1

n+1 = 2^h+1

Berúc poleno na obe strany,

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

log₂(n+1) = h+1

h = log₂(n+1) - 1

Maximálnu výšku možno vypočítať takto:

Ako vieme,

reťazec podreťazec java

n = h+1

h = n-1

Typy binárnych stromov

Existujú štyri typy binárnych stromov:

Úplný/ správny/ prísny binárny strom Kompletný binárny strom Perfektný binárny strom Degenerovaný binárny strom Vyvážený binárny strom

1. Úplný/ správny/ prísny binárny strom

Úplný binárny strom je známy aj ako striktný binárny strom. Strom možno považovať za úplný binárny strom len vtedy, ak každý uzol musí obsahovať 0 alebo 2 potomkov. Úplný binárny strom môže byť definovaný aj ako strom, v ktorom každý uzol musí obsahovať 2 potomkov okrem listových uzlov.

Pozrime sa na jednoduchý príklad plného binárneho stromu.

Vo vyššie uvedenom strome môžeme pozorovať, že každý uzol obsahuje nula alebo dve deti; preto je to úplný binárny strom.

Vlastnosti úplného binárneho stromu

• Počet listových uzlov sa rovná počtu vnútorných uzlov plus 1. Vo vyššie uvedenom príklade je počet vnútorných uzlov 5; preto sa počet listových uzlov rovná 6.
• Maximálny počet uzlov je rovnaký ako počet uzlov v binárnom strome, t.j. 2^h+1-1.
• Minimálny počet uzlov v úplnom binárnom strome je 2*h-1.
• Minimálna výška plného binárneho stromu je log₂(n+1) - 1.
• Maximálnu výšku celého binárneho stromu možno vypočítať ako:

n = 2*h - 1

n+l = 2*h

h = n+1/2

Kompletný binárny strom

Kompletný binárny strom je strom, v ktorom sú všetky uzly úplne vyplnené okrem poslednej úrovne. V poslednej úrovni musia byť všetky uzly čo najľavejšie. V úplnom binárnom strome by sa uzly mali pridávať zľava.

Vytvorme kompletný binárny strom.

Vyššie uvedený strom je úplný binárny strom, pretože všetky uzly sú úplne vyplnené a všetky uzly v poslednej úrovni sú pridané vľavo ako prvé.

Vlastnosti kompletného binárneho stromu

• Maximálny počet uzlov v kompletnom binárnom strome je 2^h+1- 1.
• Minimálny počet uzlov v úplnom binárnom strome je 2^h.
• Minimálna výška úplného binárneho stromu je log₂(n+1) - 1.
• Maximálna výška úplného binárneho stromu je

Perfektný binárny strom

java do while príklad

Strom je dokonalý binárny strom, ak všetky vnútorné uzly majú 2 potomkov a všetky listové uzly sú na rovnakej úrovni.

Pozrime sa na jednoduchý príklad dokonalého binárneho stromu.

Nižšie uvedený strom nie je dokonalý binárny strom, pretože všetky uzly listov nie sú na rovnakej úrovni.

Poznámka: Všetky dokonalé binárne stromy sú úplné binárne stromy, ako aj úplný binárny strom, ale naopak to neplatí, t. j. všetky úplné binárne stromy a úplné binárne stromy sú dokonalé binárne stromy.

Degenerovaný binárny strom

Degenerovaný binárny strom je strom, v ktorom majú všetky vnútorné uzly iba jedného potomka.

Poďme pochopiť zdegenerovaný binárny strom prostredníctvom príkladov.

Vyššie uvedený strom je degenerovaný binárny strom, pretože všetky uzly majú iba jedno dieťa. Je tiež známy ako strom skosený doprava, pretože všetky uzly majú iba pravé dieťa.

Vyššie uvedený strom je tiež zdegenerovaný binárny strom, pretože všetky uzly majú iba jedno dieťa. Je tiež známy ako strom skosený doľava, pretože všetky uzly majú iba ľavé dieťa.

Vyvážený binárny strom

Vyvážený binárny strom je strom, v ktorom sa ľavý a pravý strom líšia najviac o 1. Napríklad AVL a Červeno-čierne stromy sú vyvážené binárne stromy.

Poďme pochopiť vyvážený binárny strom prostredníctvom príkladov.

Vyššie uvedený strom je vyvážený binárny strom, pretože rozdiel medzi ľavým a pravým podstromom je nula.

Vyššie uvedený strom nie je vyvážený binárny strom, pretože rozdiel medzi ľavým podstromom a pravým podstromom je väčší ako 1.

Implementácia binárneho stromu

Binárny strom je implementovaný pomocou ukazovateľov. Prvý uzol v strome je reprezentovaný koreňovým ukazovateľom. Každý uzol v strome pozostáva z troch častí, t. j. údajov, ľavého ukazovateľa a pravého ukazovateľa. Aby sme vytvorili binárny strom, musíme najprv vytvoriť uzol. Vytvoríme užívateľsky definovaný uzol, ako je uvedené nižšie:

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

Vo vyššie uvedenej štruktúre údajov je hodnota, ľavý ukazovateľ obsahuje adresu ľavého uzla a pravý ukazovateľ obsahuje adresu pravého uzla.

uložiť video z youtube vlc

Program binárneho 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; } } 

Vyššie uvedený kód volá funkciu create() rekurzívne a vytvára nový uzol pri každom rekurzívnom volaní. Keď sú vytvorené všetky uzly, vytvorí sa binárna stromová štruktúra. Proces návštevy uzlov je známy ako prechod cez strom. Na návštevu uzla sa používajú tri typy prechodov:

• Neriadkový prechod
• Prechod predobjednávky
• Prenos poštovej poukážky