Sisäsolmuja

Sisäsolmuja tarkoittaa puun rakennekerroksessa solmua, jolla on ainakin yksi lapsi. Puun juurikin voidaan katsoa sisäsolmuksi tai lehtisolmuksi riippuen siitä, onko sillä lapsia. Lehtisolmut (lehtisolmuja) puolestaan ovat solmuja, joilla ei ole lainkaan lapsia.

Yleisesti ottaen finite rootatun puun solmut jaetaan sisäsolmuihin ja lehtisolmuihin, ja kaikkien solmujen summa on puun kokonaismäärä. Jos N on puun kokonaismäärä solmuja, I sisäsolmujen määrä ja L lehtisolmujen määrä, niin N = I + L. Tästä seuraa, että I = N − L. Erityisissä tapauksissa, kuten täsmälleen kahdella lapsella jokaisella sisäsolmulla varustetussa täysbinäärisessä puussa, pätee L = I + 1, eli lehtisolmujen määrä on yhden enemmän kuin sisäsolmujen määrä.

Käyttökohteet ja esimerkit: sisäsolmuja esiintyy laajalti tietorakenteissa ja ohjelmoinnissa. Esimerkkejä ovat binäärihakupuut ja muut hakupuut, B-puut sekä lausekepuut ja syntaksipuut, joissa sisäsolmut muodostavat puun rakenneosat ja lehtisolmuilla on lopulliset arvot tai operoidavat lapset. Biologian filogiapuut käyttävät myös sisäsolmuja viittaamaan hypoteettisiin esi-isiin. Sisäsolmujen määrä ja sijoittuminen vaikuttavat puun tilavuuteen, korkeuteen ja operaatioiden aikavaativuuksiin sekä tallennustarpeeseen.