“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

Дарахт “кўриги” процедурлари 
Бинар дарахти берилган бўлсин:
Бинар дарахтлари кўригини учта тамойили мавжуд. Уларни берилган дарахт мисолида кўриб чиқайлик: 
1) Юқоридан пастга кўрик (дарахт илдизини қисм дарахтларга нисбатан олдинроқ кўрикдан 
ўтказилади): A, B, C ; 
2) Чапдан ўнга: B, A, C ; 
3) Қуйидан юқорига (илдиз қисм дарахтлардан кейин кўрилади): B, C, A . 
Дарахт кўриги энг кўп иккинчи усул билан, яъни тугунларга кириш уларнинг калит қийматларини 
ўсиш тартибида амалга оширилади. 
Дарахт кўригини рекурсив процедурлари:
1) PROCEDURE pretrave (tree) 
IF tree<>nil 
THEN PRINT info (tree) 
pretrave (left (tree)) 
pretrave (right (tree)) 
END IF 
RETURN 
2) PROCEDURE intrave (tree) 
IF tree<>nil 
THEN intrave (left (tree)) 

---

25
PRINT info (tree) 
intrave (right (tree)) 
END IF 
RETURN 
3) PROCEDURE postrave (tree) 
IF tree<>nil 
THEN postrave (left (tree)) 
postrave (right (tree)) 
PRINT info (tree) 
END IF 
RETURN 
 
Бинар дарахт бўйича қидирув процедураси 
Мазкур процедуранинг вазифаси шундан иборатки, у берилган калит бўйича дарахт тугуни қидирувини 
амалга оширади. Қидирув операциясининг давомийлиги дарахт тузилишига боғлиқ бўлади. Ҳақиқатдан, агар 
элементлар дарахтга калит қийматлари ўсиш (камайиш) тартибида келиб тушган бўлса, у ҳолда дарахт бир 
томонга йўналган рўйхат ҳосил қилади (чиқиш даражаси бир бўлади, яъни ягона шоҳга эга), масалан: 
Бу ҳолда дарахтда қидирув вақти, бир томонлама йўналтирилган рўйхатдаги каби бўлиб, ўртача қараб 
чиқишлар сони N/2 бўлади. 
Агар дарахт мувозанатланган бўлса, у ҳолда қидирув энг самарали натижа беради. Бу ҳолда қидирув 
N
2
log
дан кўп бўлмаган элементларни кўриб чиқади. 
Қидирув процедурасини кўриб чиқамиз. search ўзгарувчисига топилган бўғин кўрсаткичи 
ўзлаштирилади: 
p=tree 
WHILE p<>nil DO 
IF key=k (p) 
THEN search=p 
RETURN 
END IF 
IF key<>k (p) 
THEN p=left (p) 
ELSE p=right (p) 
END IF 
END WHILE 
search=nil 
RETURN