Maxmasoatova faridaning algoritmlarni loyihalash fanidan tayyorlagan

Daraxt haqida tushuncha
Daraxt ta'rifi tabiatan rekursivdir. Ushbu ma'lumotlar strukturasining elementi deyiladiyuqori . Daraxt - bu cheklangan miqdordagi bog'langan vertex (filiallari , boshqa daraxtlar). Hozirgi tepalik uchun joylashgan daraxtlar deyiladipastki daraxtlar va ularning boshlariavlodlar . Avlodlarga nisbatan hozirgi tepalik deyiladiajdod . Farzandlari bo'lmagan vertikalar barg yoki deyiladiterminal, butun daraxtning bosh tepasi deyiladiildiz .
Daraxtning rekursiv ta'rifi, u bilan ishlash algoritmlari ham rekursiv bo'lishiga olib keladi. Tsiklik algoritmlar aslida mumkin, ammo ular tanlov asosida chiziqli rekursiyaning natijasidir. Birinchi bosqichda biz algoritmning umumiy shaklini aniqlaymiz,daraxtning to'liq rekursiv o'tishi, bu daraxtning vakillik shakliga bog'liq emas. Uning g'oyasi shundaki , tepada bajarilgan har qanday harakat, shuningdek, uning barcha kichik daraxtlariga nisbatan bajarilishi kerak, ya'ni algoritm ushbu tepalikning barcha avlodlariga nisbatan rekursiv ravishda bajarilishi kerak. Parametr sifatida joriy tepalikning identifikatori (indeks, ko'rsatgich, havola) talab qilinadi.

Daraxt tuzilmalari haqida gap ketganda, ularning mavhum ta'rifini ularni xotirada amalga oshirishning aniq usulidan ajratish kerak. Ikkinchisi daraxt bilan ishlaydigan algoritmlarning turiga ham bog'liq:
- agar daraxtning ildiz tugunidan ishlay boshlaydigan rekursiv yoki tsiklik algoritm ishlatilsa, u holda faqat ajdoddan avlodlarga to'g'ridan-to'g'ri bog'lanishlar kerak;
- agar algoritm daraxt bo'ylab yuqoriga va pastga (masalan, daraxtga o'xshash katalog tizimida) barcha yo'nalishlarda harakatlanishni nazarda tutsa, u holda avlodlardan ajdodlarga oldinga va orqaga yo'naltirilgan bog'lanishlar mavjud ( katalog tizimi, ota-onalar katalogiga havola);
- Terminal tepalaridan boshlab daraxt bilan ishlaydigan algoritmlar mumkin. Keyinchalik, avlodlardan ajdodlarga bog'lanishdan tashqari, terminal tugunlarini birlashtiradigan ma'lumotlar tuzilishi ham kerak (masalan, ko'rsatgichlar qatori).