Binäärinen puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. heinäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Binääripuu  on hierarkkinen tietorakenne , jossa kullakin solmulla on enintään kaksi jälkeläistä (lapsta). Tyypillisesti ensimmäistä solmua kutsutaan pääsolmuksi, ja lapsia kutsutaan vasemmaksi ja oikeaksi lapsiksi. Binääripuu on järjestetty suunnattu puu [1] .

Käytännön syistä käytetään yleisesti kahta binääripuiden alatyyppiä - binäärihakupuuta ja binaarikasaa .

Rekursiivinen määritelmä

Binääripuulle on olemassa seuraava rekursiivinen määritelmä (katso BNF ):

<binääripuu> ::= ( <data> <binääripuu> <binääripuu> ) | tyhjä .

Toisin sanoen binääripuu on joko tyhjä tai koostuu tiedosta ja kahdesta alipuusta (joista jokainen voi olla tyhjä). Ilmeinen mutta tärkeä tosiasia on ymmärtää, että jokainen osapuu on puolestaan ​​myös puu. Jos solmussa on molemmat tyhjät alipuut, sitä kutsutaan lehtisolmuksi (leaf vertex) tai lehtisolmuksi (pääte) [2] .

Esimerkiksi kuvassa oikealla näkyvä. 1 puu tämän kieliopin mukaan voitaisiin kirjoittaa näin:

(m (e (c (nolla nolla) tyhjä ) (g tyhjä (k null tyhjä) ) ) (s (p (o null null) (s null null) ) (y tyhjä) ) )

Jokainen puun solmu määrittelee alipuun , jonka juuri se on. Solmussa m = (data, vasen, oikea) on kaksi lasta (vasen ja oikea) vasemmalla ja oikealla ja vastaavasti kaksi alipuuta (vasen ja oikea), joiden juuret ovat vasemmalla ja oikealla [3] .

Sovellus

Monet hyödylliset tietorakenteet perustuvat binääripuuhun:

Muistiinpanot

  1. ↑ Binääripuu. . kvodo.ru. Haettu 1. maaliskuuta 2019. Arkistoitu alkuperäisestä 2. maaliskuuta 2019.
  2. ↑ Puu . Haettu 1. maaliskuuta 2019. Arkistoitu alkuperäisestä 2. maaliskuuta 2019.
  3. ↑ Binäärihakupuut: Johdanto . algolist.manual.ru. Haettu 1. maaliskuuta 2019. Arkistoitu alkuperäisestä 14. heinäkuuta 2019.

Linkit