Ma’ruzalar. Binar daraxtlar Reja
Download 0.53 Mb. Pdf ko'rish
|
16-17 Binar daraxtlar
- Bu sahifa navigatsiya:
- Kalitli so’zlar
- Daraxtlar Daraxt – bu chiziqsiz bog’langan ma’lumotlar tuzilmasidir (qarang, chizma).
|
16-17-ma’ruzalar. Binar daraxtlar Reja. 1. Daraxtlar. Ularni tasvirlash. 2. Binar daraxtlar. 3. Ko’p o’lchamli daraxtni binar ko’rinishga keltirish. 4. Daraxtlar ustidagi amallar. Kalitli so’zlar: rekursiya,rekursiv algoritm, rekursiv tuzilma, daraxt, ko’p o’lchamli daraxt, binar daraxt, ildiz, ota-o’g’il, terminal (barg), daraxt balandligi, chiqish darajasi, muvozanatlangan daraxt, kalit, daraxt qurish, tugun qo’shish, o’chirish, qidirish, daraxt ko’ruvi, daraxtlarni tasvirlash. Daraxtlar Daraxt – bu chiziqsiz bog’langan ma’lumotlar tuzilmasidir (qarang, chizma). Daraxt o’zining quyidagi belgilari bilan tasniflanadi: - daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo’q. Mazkur elementga daraxt ildizi deyiladi; - daraxtda ixtiyoriy elementga chekli sondagi ko’rsatkichlar yordamida murojaat qilish mumkin; - daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni oraliq yoki terminal (barg) bo’lishi mumkin. Yuqoridagi chizmada M1, M2 - oraliq, A, B, C, D, E - barglardir. Terminal tugunning o’ziga xos tasnifi uning shoxlari yo’qligidir. Balandlik – bu daraxt bosqichi soni. Yuqoridagi chizmadagi daraxt balandligi ikkiga teng. Daraxt tugunlaridan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi (Keltirilgan chizmada M1 uchun chiqish darajasi 2, M2 uchun esa 3 ga teng). Daraxtlar chiqish darajasi bo’yicha sinflarga ajratiladi: 1) agar maksimal chiqish darajasi m bo’lsa, u holda bunday daraxt m-chi tartibli daraxt deyiladi; 2) agar chiqish darajasi 0 yoki m bo’lsa, u holda to’liq m-chi tartibli daraxt bo’ladi; 3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt binar daraxt deyiladi; 4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binar daraxt deyiladi. ugunlar orasidagi bog’liqlikni tavsiflash uchun yana quyidagicha termindan foydalaniladi: M1 – A va V elementlar uchun “ota” . A va V – esa M1 tugun “o’g’illari”. Download 0.53 Mb. Do'stlaringiz bilan baham: 
|