A Podatkovna struktura binarnega drevesa je hierarhična podatkovna struktura, v kateri ima vsako vozlišče največ dva otroka, imenovana levi in desni otrok. Običajno se uporablja v računalništvu za učinkovito shranjevanje in iskanje podatkov z različnimi operacijami, kot so vstavljanje, brisanje in prečkanje.
Uvod:
- Lastnosti binarnega drevesa
- Vrste binarnega drevesa
- Aplikacije, prednosti in slabosti binarnega drevesa
- Binarno drevo (implementacija polja)
- Popolno binarno drevo
- Popolno binarno drevo
Osnovne operacije na binarnem drevesu:
- Prehodi dreves (po vrstnem redu, pred in po vrstnem redu)
- Prehod drevesa vrstnega reda ravni
- Poiščite največjo globino ali višino danega binarnega drevesa
- Vstavljanje v binarno drevo
- Izbris v binarnem drevesu
- Naštevanje binarnih dreves
Nekaj drugih pomembnih prehodov binarnega drevesa:
- Prehod vrstnega reda ravni v spiralni obliki
- Prehod vrstnega reda obratne ravni
- BFS proti DFS za binarno drevo
- Prehod po neurejenem drevesu brez rekurzije
- Morrisov prehod za prednaročilo
- Iterativno prečkanje prednaročila
- Iterativno prečkanje po naročilu z uporabo dveh skladov
- Diagonalno prečkanje binarnega drevesa
- Prehod meje binarnega drevesa
Enostavne težave s podatkovno strukturo binarnega drevesa:
- Izračunajte globino celotnega binarnega drevesa iz prednaročila
- Izdelajte drevo iz prečkanja Inorder in Level order
- Preverite, ali je dano binarno drevo SumTree
- Preverite, ali sta vozlišči bratranca v binarnem drevesu
- Preverite, ali lahko odstranitev roba razdeli binarno drevo na dve polovici
- Preverite, ali je dano binarno drevo popolno ali ne
- Preverite, ali binarno drevo vsebuje podvojena poddrevesa velikosti 2 ali več
- Preverite, ali sta dve drevesi zrcalni
- Zložljiva binarna drevesa
- Simetrično drevo (zrcalna slika samega sebe)
- Napišite kodo za ugotavljanje, ali sta dve drevesi enaki
- Poddrevo z dano vsoto v binarnem drevesu
- Jedrnato kodiranje binarnega drevesa
- Napišite program za izračun velikosti drevesa
- Premer binarnega drevesa
- Pridobite raven vozlišča v binarnem drevesu
Srednje težave s podatkovno strukturo binarnega drevesa:
- Poiščite vsa možna binarna drevesa z danim Inorder Traversal
- Napolni naslednika po vrstnem redu za vsa vozlišča
- Konstruirajte popolno binarno drevo iz njegove predstavitve povezanega seznama
- Najmanjša zamenjava, potrebna za pretvorbo binarnega drevesa v binarno iskalno drevo
- Pretvori dano binarno drevo v dvojno povezani seznam | Komplet 1
- Pretvori drevo v gozd sodih vozlišč
- Obrni binarno drevo
- Tiskanje korenskih poti do listov brez uporabe rekurzije
- Preverite, ali so dani prehodi po predvrstnem redu, po vrstnem redu in po vrstnem redu istega drevesa
- Preverite, ali je dano binarno drevo popolno ali ne | 1. niz (iterativna rešitev)
- Preverite, ali je binarno drevo poddrevo drugega binarnega drevesa | Komplet 2
- Poiščite največjo vsoto poddrevesa v drevesu
- Največja vsota vozlišč v binarnem drevesu, tako da nobena dva nista sosednja
- Najnižji skupni prednik v binarnem drevesu | Komplet 1
- Višina generičnega drevesa iz nadrejene matrike
- Poiščite razdaljo med dvema danima ključema binarnega drevesa
Težke težave s podatkovno strukturo binarnega drevesa:
- Spremenite binarno drevo, da dobite prehod pred naročilom samo z uporabo desnih kazalcev
- Konstruirajte polno binarno drevo z uporabo njegovega prehoda po prednaročilu in prehoda po prednaročilu njegovega zrcalnega drevesa
- Konstruirajte posebno drevo iz podanega prečkanja prednaročila
- Konstruirajte drevo iz matrike prednikov
- Konstruirajte celotno k-arno drevo iz njegovega predvrstnega prehoda
- Konstruirajte binarno drevo iz niza s predstavitvijo v oklepajih
- Pretvorite binarno drevo v dvojno povezan seznam na spiralni način
- Pretvorite binarno drevo v krožni dvopovezavni seznam
- Pretvorite ternarni izraz v binarno drevo
- Preverite, ali obstaja pot od korena do lista z danim zaporedjem
- Odstranite vsa vozlišča, ki ne ležijo na nobeni poti s sum>= k
- Največja spiralna vsota v binarnem drevesu
- Vsota vozlišč na k-ti ravni v drevesu, predstavljena kot niz
- Vsota vseh števil, ki se oblikujejo od poti korena do lista
- Združite dve binarni drevesi z vsoto vozlišč (rekurzivno in iterativno)
- Poiščite koren drevesa, kjer je podana vsota ID-jev otrok za vsako vozlišče
Hitre povezave :
Priporočeno:
- Naučite se podatkovne strukture in algoritmov | Vadnica DSA