Puu
Mureakuha
Puu on tietorakennetyyppi. Ongelman määritteleminen puun muodossa helpottaa ratkaisun etsimistä. Puurakenteet mahdollistavat nopean tiedon etsinnän ja asioiden lajittelemisen.
Yleisessä puurakenteessa lasten määrä on rajoittamaton. Järjestetty puu tarkoittaa, että lapsilla on lineaarinen järjestys. Järjestämättömässä puussa lasten järjestys on mielivaltainen.
Yleisessä puurakenteessa lapsien määrää ei ole rajoitettu. Yleinen puumalli toimiikin pohjana muille eri puurakenteille, jotka tarjoavat lisää sääntöjä ja logiikkaa.
Puun solmujen läpikäynti
Puun solmuja käydään yleensä läpi ennalta määritetyn järjestyksen mukaan. Käsittelyjärjestyksiä ovat:
- Esijärjestyksessä käsitellään ensin juuri, sitten vasen alipuu ja lopuksi oikea alipuu.
- Sisäjärjestyksessä käsitellään ensin vasen alipuu, sitten juuri ja lopuksi oikea alipuu.
- Jälkijärjestyksessä käsitellaan ensin vasen alipuu, sitten oikea alipuu ja lopuksi juuri.
On myös mahdollista käsitellä solmuja tasoittain tavalla, jossa kaikki samalla tasolla olevat solmut käsitellään vasemmalta oikealle. Koska perinteisessä puussa ei ole yhteyksiä kuin lapsi- ja isäsolmuun, vaatii tämän läpikäynnin toteuttaminen muutoksia binaaripuuhun verrattuna. Binaaripuussa nimittäin lapset ovat nimetty yleensä left- tai right-lapsiksi, mutta yleisessä puussa lapsia voi olla enemmän. Eräs keino toteuttaa yleinen puu on laittaa jokaiseen solmuun tieto siitä kuinka monta lasta solmulla on. Tämän jälkeen lapsista voidaan muodostaa linkitetty lista jotta jokaiseen lapseen pääsee tarvittaessa käsiksi.
Puurakenteita
Sanastoa
- Solmu (node, vertex) on puun alkio, johon voidaan tallentaa tietoa.
- Polku on kahden solmun välinen yhteys.
- Isä (father, dad, parent) viittaa nykyistä solmua ylläolevaan solmuun.
- Lapsi on solmun alapuolella olevat solmu.
- Juuri (root) on puun aloittava solmu.
- Lehti (leaf) on solmu, jolla ei ole lapsia.
- Taso (level) viittaa syvyyteen, jolla solmu on. Juuri on tasolla nolla.
- Metsä on puu, joka sisältää alkiossaan muita puita.
