Binääripuu

Wikipedia

Yksinkertainen binääripuu jonka koko on 9 solmua ja syvyys 3, juurisolmun arvona on 2. Huomaa, että tietojenkäsittelytieteessä puu "kasvaa alaspäin".

Binääripuu on tietojenkäsittelytieteessä käytetty järjestetty puumainen tietorakenne, jonka jokaisella solmulla voi olla enintään kaksi lapsisolmua. Yleensä näitä lapsisolmuja kutsutaan nimillä vasen ja oikea. Solmua, jolla ei ole yhtään lapsisolmua kutsutaan lehdeksi.

Binääripuiden yleisin käyttötapa ovat binääriset hakupuut sekä binääriset keot.

[muokkaa] Binääripuun määritelmä

Suunnattu kaari liittää vanhemman lapseen.

Solmu jolla ei ole lapsisolmuja on lehtisolmu

Solmun n syvyys on matka juuresta solmuun. Joukkoa solmuja tietyllä syvyydellä kutsutaan joskus tasoksi.

Solmun n korkeus on matka solmusta sen kaukaisimpaan lehteen.

Solmut joilla yhteinen vanhempi kutsutaan 'sisaruksiksi'.

Jos on olemassa polku solmusta p solmuun q, niin p on q:n esivanhempi ja q on p:n jälkeläinen.

Solmun koko on sen jälkeläisten lukumäärä solmu itse mukaan lukien.

[muokkaa] Binääripuiden tyypit

Binääripuu on juurellinen puu, jossa jokaisella solmulla on enintään kaksi lasta.

Kokonainen tai aito binääripuu on juurellinen puu, jossa jokaisella solmulla on nolla tai kaksi lasta.

Täydellinen binääripuu on juurellinen puu, josa jokainen lehti on samalla syvyydellä. Toisen määritelmän mukaan täydellinen binääripuu on puu, jolla on jokainen taso alinta lukuun ottamatta täynnä ja alimman tason lehdet on järjestetty vasemmalle.

Tämä tieteeseen liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.