“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Daraxtlarni tartiblash
Daraxtlarning ikkita asosiy turi mavjud. Rekursiv daraxtda yoki tartiblanmagan daraxtda, har bir tugun uchun vorislarning tartibidan qat’iy nazar, faqat daraxtning tuzilishi muhim ahamiyatga ega.
Biror mezon asosida tartiblangan daraxt (masalan, avlodga olib boradigan har bir qirraga turli xil natural sonli qiymat berilgan) qirralari nomlangan daraxt yoki ma'lumotlar strukturasiga ega tartiblangan daraxt deyiladi.
Tartiblangan daraxtlar daraxtsimon ma’lumotlat tuzilmalari orasida eng keng tarqalgan tuzilmalardandir. Ikkilik qidiruv daraxti tartiblangan daraxt turlaridan biridir.
Daraxtlarni ifodalsh
Daraxtlarni ifodalashning turli xil usullari mavjud. Eng umumiy ifodalash usuli daraxt tugunlarini dinamik ravishda ajratilgan xotirada joylashgan yozuvlar sifatida aks ettirishdir. Bu yozuvlar tugunlarning avlodlariga, ajdodlariga (yoki ikkalasiga) murojaat qiluvchi ko'rsatkichlarni o’z ichida aks ettiradi. Daraxtlarni massiv elementlari sifatida ham ifodalash mumkin. Bunda tugunlar massivning elementlari sifatida tasvirlanadi. Tugunlar massivdagi pozitsiyalari bilan aniqlangan munosabatlar orqali bog'langan bo’ladi.
Daraxtlar graf sifatida
Graflar nazariyasida daraxt bog'langan tsiklga ega bo’lmagan grafdir (ациклический граф). Ildiz daraxt (Корневое дерево) - bu ildiz sifatida tanlangan cho’qqiga ega bo'lgan graf. Bunday holda, qirra bilan bog'langan har qanday ikkita cho'qqi ajdod munosabatlarini meros qilib oladi. Faqat daraxtlardan tashkil topgan bo’glanmagan graf o'rmon(лес) deb ataladi.
Daraxtni ko’ruv (o'tish) usullari
Ajdod tugunlari va avlod tugunlari orasidagi bog'lanishlar bo'ylab daraxt elementlarini bosqichma-bosqich ko’rib o'tish daraxtning ko’ruvi (o'tish) (обходом дерева) deb ataladi. Ko'pincha, bu jarayonni alohida tugunlar bo’ylab ko'rsatgichni yo’naltirish orqali amalga oshirish mumkin. Har bir ajdod tuguni o'z avlodlaridan oldin ko'zdan kechiriladigan ko’ruv (o'tish) oldindan tartiblangan ko’ruv (o'tish) yoki to'g'ridan-to'g'ri tartibda ko’rish (o'tish) (pre-order walk) deb ataladi va avval avlodlar, so'ngra ajdodlar ko’rib chiqilsa, keyin tartiblangan o'tish yoki teskari tartibda ko’ruv (o'tish) (post-order walk) deb ataladi. -tartibli o'tish yoki teskari tartibda o'tish (post-order yurish). Bundan tashqari, birinchi navbatda chap qism daraxtni, so'ngra tugunni, so'ngra o’ng qism daraxtni ko’rib o’tadigan simmetrik o'tish va daraja bo'yicha tugunlarni ko’rib chiqadigan kenglik bo'ylab ko’ruv (o'tish)lar mavjuddir (daraxtning N-darajasi N balandlikdagi tugunlar to'plamidir). Daraxtning har bir darajasi chapdan o'ngga qarab ko’rib chiqiladi.