"vahetippude" - 1 õppematerjal

Graafid

4 19 52 55 21 Alampuu juurt nimetatakse puu juure alluvaks. Alluvateta tippu nimetatakse leheks. Tipp y on tipust x kaugusel k kui leidub tee x= t 0,t1,...tk=y, nii et ti+1 on ti alluv. Puu I- nda taseme tippude kaugus juurest on i.Puu tipu astmeks nimetame selle tipu alluvate arvu. Tipp mis pole leht on vahetipp. Kahendpuu on täielik kui kõik lehed asuvad samal tasemel ning kõigi vahetippude aste on 2 (ehk üksikud lehed saavad olla ainult madalaimal tasemel). Järjestatud kahendpuu: Vasaku alampuu sõlmed on väiksemad ehk eespool parema alampuu sõlmedest(vaata joonist). Puu läbimine: kõigi sõlmede külastamine. Puu läbimine, Preorder järjestus. · juure külastamine · vasaku alampuu läbimine pre-order · parema alampuu läbimine pre-order eespooltoodud puu korral: 49,8,4,19,21,52,52,55 Puu läbimine, Inorder järjestus.