|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti
|
| bet | 49/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tNazorat savollar.
Rekursiya nima?
Rekursiv funksiyalar?
Rekursiv algoritmlar nima?
Rekursiv ma’lumotlar tuzilmasi nima?
Adabiyotlar.
AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 5.
9,10-ma’ruzalar. Binar daraxtlar
Reja.
Daraxtlar. Ularni tasvirlash.
Binar daraxtlar.
Ko’p o’lchamli daraxtni binar ko’rinishga keltirish.
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”.
|
| |
