Дарахтсимон тузилмалар

Натижада, ўнг ва чап қисм дарахтлари бир хил босқичли тартибланган бинар дарахт хосил қилдик.
Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари фарқи бирдан кичик бўлса, бундай дарахт идеал
мувозанатланган дарахт дейилади. Юқорида хосил қилган бинар дарахтимиз идеал мувозанатланган дарахтга
мисол бўлади.
Алгоритм
Бинар дарахт яратиш процедурси
Бинар дарахтни хосил қилиш учун ЭХМ хотирасида элементлар қуйидаги турда бўлиши лозим

P, Q – ишчи кўрсаткичлар
V=maketree(key,rec) – калит ва ёзув сегментини яратувчи процедура
P=getnode – янги элемент генерацияси
r=rec
k=key
V=P
left=nil
right=nil
tree – дарахт илдизига кўрсаткич
Бошида калит биринчи қиймати киритилади. Ундан сўнг элементн ўзини maketree процедураси орқали
ҳосил қиламиз. Кейин эса кўрсаткич бўш қийматни кўрсатгунча циклни бўйича давом эттирамиз.

Дарахт “кўриги” процедурлари
Бинар дарахти берилган бўлсин:

Бинар дарахтлари кўригини учта тамойили мавжуд. Уларни берилган дарахт мисолида кўриб чиқайлик:
1) Юқоридан пастга кўрик (дарахт илдизини қисм дарахтларга нисбатан олдинроқ кўрикдан
ўтказилади): A, B, C ;
2) Чапдан ўнга: B, A, C ;
3) Қуйидан юқорига (илдиз қисм дарахтлардан кейин кўрилади): B, C, A .
Дарахт кўриги энг кўп иккинчи усул билан, яъни тугунларга кириш уларнинг калит қийматларини
ўсиш тартибида амалга оширилади.

Бинар дарахт бўйича қидирув процедураси
Мазкур процедуранинг вазифаси шундан иборатки, у берилган калит бўйича дарахт тугуни қидирувини
амалга оширади. Қидирув операциясининг давомийлиги дарахт тузилишига боғлиқ бўлади. Ҳақиқатдан, агар
элементлар дарахтга калит қийматлари ўсиш (камайиш) тартибида келиб тушган бўлса, у ҳолда дарахт бир
томонга йўналган рўйхат ҳосил қилади (чиқиш даражаси бир бўлади, яъни ягона шоҳга эга), масалан: