· parema alampuu läbimine pre-order eespooltoodud puu korral: 49,8,4,19,21,52,52,55 Puu läbimine, Inorder järjestus. · vasaku alampuu läbimine in-order · juure külastamine · parema alampuu läbimine in-order eespooltoodud puu korral: 4,8,19,21, 49,52,52,55 Puu läbimine, Postorder järjestus. · vasaku alampuu läbimine post-order · parema alampuu läbimine post-order · juure külastamine eespooltoodud puu korral: 4,21,19,8,52,55,52,49 Kuhi Kahendpuud, mille korral on täidetud järgmised tingimused nimetame kuhjaks · kahendpuu on täielik · elemendi väärtus igas kahendpuu sõlmes pole väiksem kummagi alluva väärtusest · viimase taseme sõlmed (lehed) paiknevad järjest alates äärmisest vasakust asukohast 55 99 76 44 76 42
järjestikalgoritmi puhul halvimal juhul (n log n), keskmisel ja parimal juhul (n); "jaga ja valitse" algoritmi puhul alati (n). 1 Kahendkuhjad 26 1.2 Järjestamise kuhjameetod "Jaga ja valitse" algoritm massiivi puhul · Eeltöö -- kompaktse kahendpuu struktuuri loomine -- on triviaal- ne. Etteantud massiivi võib algusest peale käsitleda nii, nagu ta väl- jendaks kompaktset kahendpuud. Positsioonid massiivis määravad alluva-ülemuse suhted ära. · Põhitöö -- järjest suuremate alampuude muutmine kuhjaks -- on teostatav tsükliga. Läbime massiivi tagurpidi, rakendades iga elemendi juures kirje allaviimist. 1 Kahendkuhjad 27 1.2 Järjestamise kuhjameetod Järjestamine Järjend kuhjastatakse, ning tsüklis eemaldatakse kuhjast suurima võtmega kirje ja lisatakse looda-
Järjestamise kiirmeetod, samuti ühildamismeetod on divide and conquer algorithm / jaga ja valitse algoritm Which data structure is on the picture Millise andmestruktuuriga on tegemist binary heap / kahendkuhi Which order of nodes of a binary tree is generated by the following algorithm: 1) process the root node; 2) apply this algorithm to the left subtree; 3) apply this algorithm to the right subtree. Milline tippude järjestus saadakse läbides kahendpuud algoritmiga: 1) töödelda juur; 2) läbida vasak alampuu; 3) läbida parem alampuu. pre-order / eesjärjestus Which property is described as: all keys in left subtree are not greater than the key of the root node and all keys in right subtree are not less than the key of the root node. Millist omadust kirjeldab lause: kõik võtmed vasakus alampuus ei ole suuremad juure võtmest ning kõik võtmed paremas alampuus ei ole väiksemad juure võtmest.
Label 0 2 4 4 14 7 8 12 Prev A B A B C C F Lühim tee A-st H-sse: H > F > C >B > A 12 = 5 + 3 + 2 + 2 Algoritmid ja andmestruktuurid 2015 25 10. Kahendkuhi - mis teda iseloomustab, kuidas realiseeritakse, milliste ülesannete jaoks Selline kahendpuud, kus peaksid olemad täidetud järgmised tingimused: 1. Igas tipus olev väärtus ei tohi olla väiksem kui selle tipu järglastel 2. Lehtede sügavus ei tohi erineda rohkem kui 1 taseme võrra 3. Viimane tase täitub vasakult paremale • Andmestruktuur on tavaliselt realiseeritud massiivina ja puu juur on element indeksiga 1, edasi tulevad juure järglased 2 ja 3 jne • Kahendkuhja kasutatakse ka prioriteetidega järjekorra realiseerimiseks.
annaabi.ee 
