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

"ДАРАХТСИМОН ТУЗИЛМАЛАР"
Ишдан мақсад: бинар дарахтлар билан ишлашда фойдаланиладиган процедураларни тадқиқ қилиш ва ўрганиш.
Қўйилган масала: Бинар дарахтларни тадқиқ қилишга оид дастурни яратиш кўникмасига эга бўлиш.
Иш тартиби:
Тажриба иши тавсифини ўрганиш;
Берилган топшириқни дастури алгоритмини ишлаб чиқиш;
С++ тилида дастурни яратиш;
Дастурни ишлатиш;
натижани олиш;
хисоботни тайёрлаш.
Қисқача назария
Дарахт кўринишидаги маълумотлар тузилмаси ҳақида умумий тушунчалар.
Дарахт – бу шундай чизиқсиз боғланган маълумотлар тузилмасики, у қуйидаги белгилари билан
тавсифланади:
- дарахтда шундай битта элемент борки, унга бошқа элементлардан мурожаат йўқ. Бу элемент дарахт
илдизи дейилади;
- дарахтда ихтиёрий элементга чекли сондаги кўрсаткичлар ёрдамида мурожаат қилиш мумкин;
- дарахтнинг ҳар бир элементи фақатгина ўзидан олдинги келган битта элемент билан боғланган.
Дарахтнинг ҳар бир тугуни оралиқ (2, 3, 5, 7 элементлар) ёки терминал (дарахт “барг”и) (4, 9, 10, 11, 8,
6 элементлар) бўлиши мумкин. Терминал тугуннинг ўзига хос таснифи унинг шохлари йўқлигидир.

Х элементнинг бевосита пастида жойлашган У элемент, Х нинг бевосита авлоди деб аталди. Агар X i
босқичда бўлса, у ҳолда Y i+1 босқичда ётади дейилади .
Бинар дарахтларн қуриш
Бинар дарахтда хар бир тугун-элементдан кўпи билан 2 та шох
Дарахтларни ЭХМ хотирасида тасвирланишига кўра хар бир элемент (бинар дарахт тугуни) тўртта
майдонга эга ёзув бўлади. Мазкур майдонлар қиймати мос равишда ёзув калити бўлиб, бошқа элементларга
мурожаатни ифодалайди, яъни чапга-пастга, ўнга-пастга ва ёзув матнига.
Шуни эсда тутиш лозимки, дарахт хосил қилинаётганда, отага нисбатан чап томондаги ўғил қиймати
кичик калитга, ўнг томондаги ўғил эса катта қийматли калитга эга бўлади.
Масалан, дарахт тугунлари қуйидаги қийматларга эга 6, 21, 48, 49, 52, 86, 101. У ҳолда бинар дарахт
кўриниши қуйидагича бўлади: