A Binääripuun tietorakenne on hierarkkinen tietorakenne, jossa jokaisella solmulla on korkeintaan kaksi lasta, joista käytetään nimitystä vasen lapsi ja oikea lapsi. Sitä käytetään yleisesti tietojenkäsittelytieteessä tietojen tehokkaaseen tallentamiseen ja hakemiseen erilaisilla toiminnoilla, kuten lisääminen, poistaminen ja läpikulku.
Esittely:
- Binaaripuun ominaisuudet
- Binaaripuiden tyypit
- Binaaripuun sovellukset, edut ja haitat
- Binääripuu (Array-toteutus)
- Täydellinen binääripuu
- Täydellinen binaaripuu
Binääripuun perustoiminnot:
- Tree Traversals (järjestys, ennakkotilaus ja jälkitilaus)
- Tasojärjestyspuun läpikulku
- Etsi annetun binaaripuun enimmäissyvyys tai korkeus
- Lisäys binaaripuuhun
- Poistaminen binääripuussa
- Binääripuiden luettelo
Joitakin muita tärkeitä binaaripuun läpikäyntejä:
- Tasojärjestyksen läpikulku spiraalimuodossa
- Käänteinen tasojärjestyksen läpikulku
- BFS vs DFS binaaripuulle
- Inorder Tree Traversal ilman rekursiota
- Morrisin läpikulku ennakkotilausta varten
- Iteratiivinen ennakkotilauskierros
- Iteratiivinen postorder Traversal käyttäen kahta pinoa
- Binaaripuun diagonaalinen läpikulku
- Raja Binääripuun läpikulku
Helppoja ongelmia binaaripuun tietorakenteessa:
- Laske täyden binaaripuun syvyys ennakkotilauksesta
- Rakenna puu Inorder- ja Level-järjestyksen läpikäynneistä
- Tarkista, onko tietty binaaripuu SumTree
- Tarkista, ovatko kaksi solmua serkkuja binääripuussa
- Tarkista, voiko reunan poistaminen jakaa binaaripuun kahteen puolikkaaseen
- Tarkista, onko annettu binääripuu täydellinen vai ei
- Tarkista, sisältääkö binääripuu päällekkäisiä alipuita, joiden koko on 2 tai suurempi
- Tarkista, ovatko kaksi puuta peilikuvia
- Taitettavat binaaripuut
- Symmetrinen puu (peilikuva itsestään)
- Kirjoita koodi määrittääksesi, ovatko kaksi puuta identtisiä
- Alipuu tietyllä summalla binääripuussa
- Binaaripuun ytimekäs koodaus
- Kirjoita ohjelma puun koon laskemiseksi
- Binääripuun halkaisija
- Hanki solmun taso binaaripuussa
Keskikokoiset ongelmat binääripuun tietorakenteessa:
- Etsi kaikki mahdolliset binääripuut annetulla Inorder Traversalilla
- Täytä Inorder Successor kaikille solmuille
- Rakenna täydellinen binaaripuu sen linkitettyjen luetteloiden esityksestä
- Vähimmäisvaihto, joka tarvitaan binääripuun muuntamiseen binäärihakupuuksi
- Muunna tietty binääripuu kaksoislinkitetyksi luetteloksi | Sarja 1
- Muunna puu parillisten solmujen metsäksi
- Käännä binaaripuu
- Tulosta juuresta lehtiin polut ilman rekursiota
- Tarkista, ovatko annetut ennakkotilaus-, tilaus- ja jälkikävitykset samasta puusta
- Tarkista, onko tietty binaaripuu valmis vai ei | Sarja 1 (Iteratiivinen ratkaisu)
- Tarkista, onko binääripuu toisen binääripuun alipuu | Sarja 2
- Etsi puun suurin alipuusumma
- Binaaripuun solmujen maksimisumma siten, ettei kahta vierekkäistä ole
- Alin yhteinen esi-isä binaaripuussa | Sarja 1
- Yleisen puun korkeus ylätason taulukosta
- Etsi etäisyys binääripuun kahden annetun avaimen välillä
Vaikeita ongelmia binääripuun tietorakenteessa:
- Muokkaa binaaripuuta saadaksesi ennakkotilauksen läpikulkua käyttämällä vain oikeita osoittimia
- Muodosta täysi binääripuu käyttämällä sen ennakkotilausläpikulkua ja peilipuun ennakkotilausläpikulkua
- Rakenna erityinen puu annetusta ennakkotilauksesta
- Rakenna puu esivanhemmatriisista
- Muodosta täysi k-aaripuu sen ennakkotilauksen läpikäymisestä
- Muodosta binääripuu merkkijonosta hakasulkeiden esityksellä
- Muunna binääripuu kaksinkertaisesti linkitetyksi luetteloksi spiraalimaisesti
- Muunna binääripuu pyöreäksi kaksoislinkkiluetteloksi
- Muunna kolmiulotteinen lauseke binääripuuksi
- Tarkista, onko polkua juuresta lehtiin tietyllä järjestyksellä
- Poista kaikki solmut, jotka eivät ole missään polussa summa>= k:lla
- Suurin spiraalisumma binääripuussa
- Solmujen summa k:nnellä tasolla puussa, joka esitetään merkkijonona
- Kaikkien numeroiden summa, jotka muodostuvat juuresta lehtiin
- Yhdistä kaksi binaaripuuta tekemällä solmusumma (rekursiivinen ja iteratiivinen)
- Etsi puun juuri, jossa kunkin solmun lasten id-summa on annettu
Pikalinkit:
Suositus:
- Opi tietorakenne ja algoritmit | DSA opetusohjelma