Čo je úplný binárny strom?

Úplný binárny strom možno definovať ako a binárny strom v ktorej majú všetky uzly 0 alebo dve deti. Inými slovami, úplný binárny strom možno definovať ako binárny strom, v ktorom majú všetky uzly dvoch potomkov okrem listových uzlov.

Nižšie uvedený strom je úplný binárny strom:

Vyššie uvedený strom je úplný binárny strom, pretože všetky uzly okrem listových uzlov majú dvoch potomkov.

Úplná veta o binárnom strome:

Považujte binárny strom T za neprázdny strom, potom:

• Nech som vnútornými uzlami v strome a L ako listovým uzlom v strome, potom by sa počet listových uzlov rovnal:
  L = I + 1
• Ak má T, I počet vnútorných uzlov a N je celkový počet uzlov, potom by sa celkový počet uzlov rovnal:
  N = 21 + 1
• Ak T obsahuje 'N' celkový počet uzlov a 'I' je počet interných uzlov, potom by sa počet interných uzlov rovnal:
  I = (N-1)/2
• Ak 'T' má 'N' celkový počet uzlov a 'L' je počet listových uzlov, potom by sa počet listových uzlov rovnal:
  L = (N+l)/2
• Ak 'T' obsahuje 'L' počet listových uzlov, potom by sa celkový počet uzlov rovnal:
  N = 2 1 - 1
• Ak má 'T' počet listových uzlov 'L' a 'I' je počet vnútorných uzlov, počet vnútorných uzlov by sa rovnal:
  I = L - 1

Čo je úplný binárny strom?

Binárny strom sa považuje za úplný binárny strom, keď sú všetky úrovne úplne zaplnené okrem poslednej úrovne, ktorá sa vypĺňa zľava.

vlk alebo líška

Nižšie uvedený strom je úplný binárny strom:

Úplný binárny strom je podobný úplnému binárnemu stromu s výnimkou dvoch rozdielov, ktoré sú uvedené nižšie:

• Plnenie uzla listu musí začínať od krajnej ľavej strany.
• Nie je povinné, že posledný listový uzol musí mať správneho súrodenca.

Poďme pochopiť vyššie uvedené body na príklade:

seriál v postgrese

Zvážte nižšie uvedený strom:

Vyššie uvedený strom je úplný binárny strom, ale nie úplný binárny strom, pretože uzol 6 nemá svojho pravého súrodenca.

Vytvorenie kompletného binárneho stromu

Predpokladajme, že máme pole 6 prvkov znázornených nižšie:

Vyššie uvedené pole obsahuje 6 prvkov, t. j. 1, 2, 3, 4, 5, 6. Nasledovné sú kroky, ktoré je potrebné použiť na vytvorenie úplného binárneho stromu:

Krok 1: Najprv vyberieme prvý prvok poľa, t.j. 1, a vytvoríme koreňový uzol stromu. Počet prvkov dostupných v prvej úrovni je 1.

Krok 2: Teraz vyberieme druhý a tretí prvok poľa. Ponechajte druhý prvok a tretí prvok poľa ako ľavý a pravý potomok koreňového uzla, ako je znázornené nižšie:

Ako môžeme vidieť vyššie, počet prvkov dostupných v druhej úrovni je 2.

Krok 3: Teraz vyberieme ďalšie dva prvky z poľa, t. j. 4 a 5. Ponechajte tieto dva prvky naľavo a napravo od uzla 2, ako je znázornené nižšie:

Ako môžeme pozorovať vyššie, uzly 4 a 5 sú ľavým a pravým potomkom uzla 2.

javascript onload skript

Krok 4: Teraz vyberieme posledný prvok poľa, t. j. 6, a ponecháme ho ako ľavý potomok uzla 3, pretože vieme, že v úplnom binárnom strome sú uzly vyplnené z ľavej strany, ako je znázornené nižšie:

Ako môžeme pozorovať, druhá úroveň obsahuje 3 prvky.

Poďme pochopiť rozdiely medzi úplným a úplným binárnym stromom prostredníctvom obrázkov.

1. Binárny strom, ktorý je zobrazený nižšie, nie je úplný ani úplný binárny strom. Nie je to úplný binárny strom, pretože uzol 3 má iba jedného potomka. Tiež to nie je úplný binárny strom, pretože uzly by sa mali vyplniť z ľavej strany, ale uzol 3 má pravé dieťa a nemá ľavé dieťa.
   
2. Binárny strom, ktorý je zobrazený nižšie, je úplný binárny strom, ale nie úplný binárny strom. Je to úplný binárny strom, pretože všetky uzly majú buď 0 alebo 2 deti. Nie je to úplný binárny strom, pretože uzol 3 nemá žiadne deti, zatiaľ čo uzol 2 má svojich potomkov a vieme, že uzly by sa mali vyplniť z ľavej strany v úplnom binárnom strome.
   
3. Binárny strom, ktorý je uvedený nižšie, je úplný binárny strom, ale nie úplný binárny strom. Je to úplný binárny strom, pretože všetky uzly zostávajú vyplnené. Nie je to úplný binárny strom, pretože uzol 2 má iba jedného potomka.
   
4. Binárny strom, ktorý je zobrazený nižšie, je úplný, ako aj úplný binárny strom. Je to úplný binárny strom, pretože všetky uzly zostávajú vyplnené. Je to úplný binárny strom, pretože všetky uzly majú buď 0 alebo 2 deti.