Ma’ruzalar. Binar daraxtlar Reja


Download 62.91 Kb.
Pdf ko'rish
bet1/6
Sana23.11.2023
Hajmi62.91 Kb.
#1795890
  1   2   3   4   5   6
Bog'liq
Tema16-17 (2)



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 62.91 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling