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

Ma’lumotlar tuzilmasi va Algoritmlar fani
SWD 030-L3 guruh talabasi

Axrorov Shuhratbek

5-labaratoriya ishi.

"ДАРАХТСИМОН ТУЗИЛМАЛАР"
Дарахт кўринишидаги маълумотлар тузилмаси ҳақида умумий тушунчалар.

Дарахт – бу шундай чизиқсиз боғланган маълумотлар тузилмасики, у қуйидаги белгилари билан тавсифланади:

- дарахтда шундай битта элемент борки, унга бошқа элементлардан мурожаат йўқ. Бу элемент дарахт илдизи дейилади;

- дарахтда ихтиёрий элементга чекли сондаги кўрсаткичлар ёрдамида мурожаат қилиш мумкин;

- дарахтнинг ҳар бир элементи фақатгина ўзидан олдинги келган битта элемент билан боғланган.

Дарахтнинг ҳар бир тугуни оралиқ (2, 3, 5, 7 элементлар) ёки терминал (дарахт “барг”и) (4, 9, 10, 11, 8, 6 элементлар) бўлиши мумкин. Терминал тугуннинг ўзига хос таснифи унинг шохлари йўқлигидир.

Х элементнинг бевосита пастида жойлашган У элемент, Х нинг бевосита авлоди деб аталди. Агар X i босқичда бўлса, у ҳолда Y i+1 босқичда ётади дейилади .

Бинар дарахтларн қуриш

Бинар дарахтда хар бир тугун-элементдан кўпи билан 2 та шох

Дарахтларни ЭХМ хотирасида тасвирланишига кўра хар бир элемент (бинар дарахт тугуни) тўртта майдонга эга ёзув бўлади. Мазкур майдонлар қиймати мос равишда ёзув калити бўлиб, бошқа элементларга мурожаатни ифодалайди, яъни чапга-пастга, ўнга-пастга ва ёзув матнига.

Шуни эсда тутиш лозимки, дарахт хосил қилинаётганда, отага нисбатан чап томондаги ўғил қиймати кичик калитга, ўнг томондаги ўғил эса катта қийматли калитга эга бўлади.

Масалан, дарахт тугунлари қуйидаги қийматларга эга 6, 21, 48, 49, 52, 86, 101. У ҳолда бинар дарахт кўриниши қуйидагича бўлади:

Натижада, ўнг ва чап қисм дарахтлари бир хил босқичли тартибланган бинар дарахт хосил қилдик. Агар дарахтнинг ўнг ва чап қисм дарахтлари босқичлари фарқи бирдан кичик бўлса, бундай дарахт идеал мувозанатланган дарахт дейилади. Юқорида хосил қилган бинар дарахтимиз идеал мувозанатланган дарахтга мисол бўлади.