"alampuule" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

8.1 Puu. Üldine puu • Graaf on mittelineaarne struktuur, mille abil saab modelleerida objektide hulgas paari-kaupa esinevaid suhteid ja seoseid. • Puu on graafi erivorm. • Puus ühendatakse andmeobjektid hierhilisel viisil. • Puu koosneb elementidest, mida nim. tippudeks ehk sõlmedeks (siia paigutakse andmed/info), ja seosetest tippude (sõlmedes oleva info) vahel, mida nim. kaarteks. • Iga puu sõlm on juureks mõnele alampuule. Sõlme kõigi alampuude arvu nimetatakse selle sõlme järguks. Sõlm, mille järk on 0, on leht, Ülejäänud sõlmed on hargnevad sõlmed. • Puu sõlmed jagunevad paiknemishierarhia järgi tasemetesse. Juur on tasemel 0, juure järglased on tasemel 1 jne. Vastavalt tasemete arvule mõõdetakse ka puu kõrgust. • Puu on täielik, kui tema kõigil tasemetel on max võimalik arv sõlmi ja kõik lehed paiknevad samal tasemel.