A Štruktúra údajov binárneho stromu je hierarchická dátová štruktúra, v ktorej má každý uzol najviac dvoch potomkov, označovaných ako ľavé dieťa a pravé dieťa. Bežne sa používa v informatike na efektívne ukladanie a získavanie údajov s rôznymi operáciami, ako je vkladanie, mazanie a prechádzanie.
Úvod:
- Vlastnosti binárneho stromu
- Typy binárnych stromov
- Aplikácie, výhody a nevýhody binárneho stromu
- Binárny strom (implementácia poľa)
- Kompletný binárny strom
- Perfektný binárny strom
Základné operácie na binárnom strome:
- Prechody stromov (Inorder, Preorder a Postorder)
- Prechádzanie stromom objednávky úrovne
- Nájdite maximálnu hĺbku alebo výšku daného binárneho stromu
- Vloženie do binárneho stromu
- Vymazanie v binárnom strome
- Enumerácia binárnych stromov
Niektoré ďalšie dôležité prechody binárnych stromov:
- Priebeh úrovňového poriadku v špirálovej forme
- Prechod objednávky na obrátenej úrovni
- BFS vs DFS pre binárny strom
- Inorder Tree Traversal bez rekurzie
- Morris traversal pre predobjednávku
- Iteratívne prechádzanie predobjednávky
- Iteratívne prechádzanie postorderom pomocou dvoch stohov
- Diagonálny prechod binárneho stromu
- Prechod hranicou binárneho stromu
Jednoduché problémy s dátovou štruktúrou binárneho stromu:
- Vypočítajte hĺbku celého binárneho stromu z Predobjednávky
- Zostavte strom z prechodov objednávky Inorder a Level
- Skontrolujte, či daný binárny strom je SumTree
- Skontrolujte, či sú dva uzly bratrancami v binárnom strome
- Skontrolujte, či odstránenie okraja môže rozdeliť binárny strom na dve polovice
- Skontrolujte, či je daný binárny strom dokonalý alebo nie
- Skontrolujte, či binárny strom obsahuje duplicitné podstromy veľkosti 2 alebo viac
- Skontrolujte, či sú dva stromy zrkadlové
- Skladacie binárne stromy
- Symetrický strom (zrkadlový obraz seba samého)
- Napíšte kód na určenie, či sú dva stromy totožné
- Podstrom s daným súčtom v binárnom strome
- Stručné kódovanie binárneho stromu
- Napíšte program na výpočet veľkosti stromu
- Priemer binárneho stromu
- Získajte úroveň uzla v binárnom strome
Stredné problémy s dátovou štruktúrou binárneho stromu:
- Nájdite všetky možné binárne stromy s daným Inorder Traversal
- Naplniť nástupcu poradia pre všetky uzly
- Zostavte úplný binárny strom z jeho reprezentácie prepojeného zoznamu
- Minimálny swap potrebný na konverziu binárneho stromu na binárny vyhľadávací strom
- Previesť daný binárny strom na zoznam s dvojitým prepojením | Set 1
- Preveďte strom na les párnych uzlov
- Prevrátiť binárny strom
- Vytlačte cesty od koreňov k listom bez použitia rekurzie
- Skontrolujte, či dané prechody Preorder, Inorder a Postorder sú z rovnakého stromu
- Skontrolujte, či je daný binárny strom úplný alebo nie | Sada 1 (opakované riešenie)
- Skontrolujte, či je binárny strom podstrom iného binárneho stromu | Súprava 2
- Nájdite najväčšiu sumu podstromu v strome
- Maximálny súčet uzlov v binárnom strome tak, aby žiadne dva nesusedili
- Najnižší spoločný predok v binárnom strome | Set 1
- Výška generického stromu z nadradeného poľa
- Nájdite vzdialenosť medzi dvoma danými kľúčmi binárneho stromu
Ťažké problémy s dátovou štruktúrou binárneho stromu:
- Upravte binárny strom, aby ste získali prechod Predobjednávky iba pomocou pravých ukazovateľov
- Zostavte úplný binárny strom pomocou prechodu predobjednávky a prechodu predobjednávky jeho zrkadlového stromu
- Zostavte špeciálny strom z daného prechodu predobjednávky
- Zostrojte strom z matice predkov
- Zostavte celý strom k-ary z prechodu predobjednávky
- Zostavte binárny strom z reťazca s reprezentáciou zátvoriek
- Preveďte binárny strom na dvojito prepojený zoznam špirálovitým spôsobom
- Preveďte binárny strom na kruhový zoznam dvojitých odkazov
- Previesť ternárny výraz na binárny strom
- Skontrolujte, či existuje cesta od koreňa k listu s danou sekvenciou
- Odstráňte všetky uzly, ktoré neležia na žiadnej ceste so súčtom>= k
- Maximálny špirálový súčet v binárnom strome
- Súčet uzlov na k-tej úrovni v strome reprezentovanom ako reťazec
- Súčet všetkých čísiel, ktoré sa tvoria od koreňových po listové cesty
- Zlúčte dva binárne stromy vykonaním súčtu uzlov (rekurzívne a iteratívne)
- Nájdite koreň stromu, kde je uvedený súčet ID detí pre každý uzol
Rýchle odkazy:
Odporúčané:
- Naučte sa dátovú štruktúru a algoritmy | Príručka DSA