In graafiteoria , joka on juurtunut puu tai arborescence on suunnattu asyklinen kaavio , jossa on yksi juuri, ja siten, että kaikki solmut paitsi juuri on yksi vanhempi.
In Computer Science , se on myös rekursiivinen tietorakenne käytetään edustamaan tämän kuvaajan tyyppi.
Puussa on kaksi elementtiluokkaa:
Juurta puun on ainoa solmu, joka ei ole vanhempi. Solmut (isät poikiensa kanssa) on kytketty toisiinsa harjanteen avulla . Kontekstista riippuen solmu voi viitata puun sisäiseen tai ulkoiseen solmuun (lehti).
Syvyys solmun on etäisyys, eli reunojen lukumäärän, juuresta solmuun. Korkeus puun on suurin syvyys lehtiä puussa. Koko puun on sen solmujen lukumäärä (laskien lehdet tai ei), polun pituus on summa syvyyksistä kunkin lehtiä.
Puut voidaan merkitä. Tässä tapauksessa jokaisella solmulla on tarra , joka on eräänlainen solmun "sisällöstä". Tunniste voi olla hyvin yksinkertainen: esimerkiksi kokonaisluku. Se voi myös olla niin monimutkainen kuin haluat: objekti, tietorakenteen esiintymä, osoitin jne. Lähes aina on pakollista pystyä vertaamaan tarroja kokonaisjärjestyksen suhteen mukaan algoritmien toteuttamiseksi puissa.
Tiedostoja ja kansioita tiedostojärjestelmän järjestetään yleensä puurakenne. Katso esimerkiksi FHS .
Puuta käytetään itse asiassa harvoin sellaisenaan, mutta on olemassa monia rajoittavamman rakenteen puulajeja, joita käytetään yleisesti algoritmeissa , erityisesti tietokantojen hallinnassa tai tiedostojen indeksoinnissa. Sitten ne mahdollistavat nopeat ja tehokkaat haut. Tässä annamme sinulle tärkeimmät esimerkit:
Voit rakentaa puun vain tietoja sisältävistä laatikoista jollakin seuraavista kolmesta tavasta:
Huomaa, että puiden erityistapauksissa on erityyppisiä esitystapoja. Esimerkiksi kasaa edustaa joukko tarroja.
Puu kävelylenkit ovat kärkipisteet vierailuja käsitellä puun, esimerkiksi löytää arvoa.
Leveys polku vastaa polun tason solmujen puun. Taso on joukko sisäisiä solmuja tai lehtiä, jotka sijaitsevat samalla syvyydellä - puhumme myös saman korkeuden solmusta tai lehdestä tarkasteltavassa puussa. Tietyn tason selausjärjestys annetaan yleensä rekursiivisesti vanhempien solmujen - seuraavan ylemmän tason solmujen - selausjärjestyksessä.
Näin ollen, jos edellinen puu käytetään, reitti on , B , C , D , E , F ja G .
Perusteellinen reitillä on rekursiivinen reitti puussa. Yleensä kaksi tilausta on mahdollista:
Binaaripuille voimme tehdä myös infix-polun , ts. Käsitellä nykyistä solmua vasemman ja oikean solmun välillä. Näin ollen, jos edellinen puu käytetään, reitti on D , B , E , , F , C ja G .