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

Қисқача назария 
Дарахт кўринишидаги маълумотлар тузилмаси ҳақида умумий тушунчалар. 
Дарахт – бу шундай чизиқсиз боғланган маълумотлар тузилмасики, у қуйидаги белгилари билан 
тавсифланади: 
- дарахтда шундай битта элемент борки, унга бошқа элементлардан мурожаат йўқ. Бу элемент дарахт 
илдизи дейилади; 
- дарахтда ихтиёрий элементга чекли сондаги кўрсаткичлар ёрдамида мурожаат қилиш мумкин; 
- дарахтнинг ҳар бир элементи фақатгина ўзидан олдинги келган битта элемент билан боғланган.
Дарахтнинг ҳар бир тугуни оралиқ (2, 3, 5, 7 элементлар) ёки терминал (дарахт “барг”и) (4, 9, 10, 11, 8, 
6 элементлар) бўлиши мумкин. Терминал тугуннинг ўзига хос таснифи унинг шохлари йўқлигидир. 
Х элементнинг бевосита пастида жойлашган У элемент, Х нинг бевосита авлоди деб аталди. Агар X i 
босқичда бўлса, у ҳолда Y i+1 босқичда ётади дейилади . 
 
Бинар дарахтларн қуриш 
Бинар дарахтда хар бир тугун-элементдан кўпи билан 2 та шох
Дарахтларни ЭХМ хотирасида тасвирланишига кўра хар бир элемент (бинар дарахт тугуни) тўртта 
майдонга эга ёзув бўлади. Мазкур майдонлар қиймати мос равишда ёзув калити бўлиб, бошқа элементларга 
мурожаатни ифодалайди, яъни чапга-пастга, ўнга-пастга ва ёзув матнига.
Шуни эсда тутиш лозимки, дарахт хосил қилинаётганда, отага нисбатан чап томондаги ўғил қиймати 
кичик калитга, ўнг томондаги ўғил эса катта қийматли калитга эга бўлади.
Масалан, дарахт тугунлари қуйидаги қийматларга эга 6, 21, 48, 49, 52, 86, 101. У ҳолда бинар дарахт 
кўриниши қуйидагича бўлади: 
Натижада, ўнг ва чап қисм дарахтлари бир хил босқичли тартибланган бинар дарахт хосил қилдик. 
Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари фарқи бирдан кичик бўлса, бундай дарахт идеал 
мувозанатланган дарахт дейилади. Юқорида хосил қилган бинар дарахтимиз идеал мувозанатланган дарахтга 
мисол бўлади. 
Алгоритм 
Бинар дарахт яратиш процедурси 
Бинар дарахтни хосил қилиш учун ЭХМ хотирасида элементлар қуйидаги турда бўлиши лозим 

---

24
P, Q – ишчи кўрсаткичлар 
V=maketree(key,rec) – калит ва ёзув сегментини яратувчи процедура 
P=getnode – янги элемент генерацияси 
r=rec 
k=key 
V=P 
left=nil 
right=nil 
tree – дарахт илдизига кўрсаткич 
Бошида калит биринчи қиймати киритилади. Ундан сўнг элементн ўзини maketree процедураси орқали 
ҳосил қиламиз. Кейин эса кўрсаткич бўш қийматни кўрсатгунча циклни бўйича давом эттирамиз. 
READ(key,rec) 
tree=maketree(key,rec) 
WHILE not eof DO 
READ(key,rec) 
V=maketree(key,rec) 
WHILE P<>nil DO 
Q=P 
IF key=k(P) 
THEN P=left(P) 
ELSE P=right(P) 
END IF 
END WHILE 
IF P=nil 
THEN WRITELN(' Бу илдиз'); 
tree=V 
ELSE IF keyTHEN left(P)=V 
ELSE right(P)=V 
END IF 
END IF 
END WHILE