11-Mavzu: Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi. Reja

Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi Daraxt - bu chiziqli bo‘lmagan bog‘lamli ma‘lumotlar tuzilmasidir.

Daraxtlar quyidagi belgilari bilan tavsiflanadi:

• 
  daraxtda ildiz deb ataluvchi shunday yagona element mavjudki, unga boshqa elementlardan murojaat mavjud emas;
  
• 
  daraxtda ixtiyoriy elementga murojaat (element qiymatini olish) chekli sondagi ketma-ket murojaatlar yoki ko‘rsatkichlardan o‘tib borish orqali amalga oshiriladi;
  
• 
  har bir element o‘zidan oldingi faqat bitta element bilan bog‘lanadi. 4.3- rasmda daraxtning tugunlari va ular orasidagi bog‘lanishlar tasvirlangan. Daraxtning ixtiyoriy tuguni oraliq tugun yoki terminal tugun (barg) bo‘lishi mumkin. 4.3-rasmdagi daraxtning M1 va M2 elementlari oraliq tugunlar, A, B, C,
  

D, E lar esa barglardir. Terminal tugunning (bargning) asosiy xususiyati undan

keyin tarmoqlanish (shoxning) yo‘qligidir.

Daraxtdagi darajalar soni balandlik deb ataladi. Masalan 4.3-rasmdagi daraxtning balandligi 2 ga teng.

Daraxtning tugunidan o‘sib chiquvchi shoxlar soni tugunning shoxlanish darajasi deyiladi. Masalan, 4.3-rasmdagi M1 uchun shoxlanish darajasi 2, M2 uchun esa 3 ga teng. SHoxlanish darajasi bo‘yicha daraxtlar quyidagi sinflarga ajratiladi:

1. 
   agar shoxlanish darajasi m ga teng bo‘lsa, bunday daraxt m-ar daraxt deyiladi;
   
2. 
   agar shoxlanish darajasi yoki 0, yoki m ga teng bo‘lsa, bunday daraxt to‘liq m-ar daraxt deyiladi;
   
3. 
   agar shoxlanish darajasining maksimal qiymati 2 ga teng bo‘lsa, bunday daraxt binar (ikkilik daraxt) deyiladi;
   
4. 
   agar shoxlanish darajasi yo 0 ga, yo 2 ga teng bo‘lsa, bunday daraxt to‘liq binar daraxt deyiladi.
   

Daraxt tugunlari o‘rtasidagi bog‘lanishlarni tavsiflash uchun ‘ota’ va ‘bola’ atamalari ishlatiladi. Masalan, 4.3-rasmdagi M1 tugun A va B elementlar uchun ‘ota’, A va B elementlar esa M1 uchun ‘bola’ hisoblanadi.

Daraxtlarni tasvirlash

Daraxtni tasavvur qilish va elementlarini qayta ishlash algoritmlarini tahlil qilishda uning chizma shaklidan foydalanish maqsadga muvofiq (4.4-rasm). Kompyuter xotirasida esa daraxtlarni bog‘lamli ro‘yxat shaklida tasvirlash ancha qulay. Bu ro‘yxatning elementlari tugunning qiymati va shoxlanish darajasi sonini saqlovchi axborot maydoniga hamda shoxlanish darajasiga teng bo‘lgan sondagi ko‘rsatkichlar maydoniga ega bo‘ladi. Elementning ixtiyoriy ko‘rsatkichi ushbu tugunni o‘zining o‘g‘il-tugunlariga yo‘naltiradi.



Daraxtning grafik va chiziqli bo’lmagan ro’yxat shakllarida tasvirlanishi

Binar (ikkilik) daraxtlar

Daraxtning eng ko‘p ishlatiladigan turlaridan biri binar daraxtdir. Daraxtni kompyuter xotirasida tasvirlashda har bir element 4 ta maydondan iborat yozuvni hosil qiladi. Bu maydonlarning qiymati mos ravishda yozuv kaliti, elementdan keyingi chap va o‘ng elementga ko‘rsatkichlar hamda yozuv qiymatidan iborat.

Binar daraxtni qurishda chap “bola” tugunga mos keluvchi yozuvning kaliti —ota” tugunga mos yozuvning kaliti qiymatidan kichik, o‘ng —bola” tugunga mos yozuvning kaliti esa - katta bo‘ladi. Misol uchun 50, 46, 61, 48, 29, 55, 79 kabi elementlardan tashkil topgan binar daraxtni qaraylik. Uning ko‘rinishi quyidagicha bo‘lsin:

Binar daraxtni hosil qilish uchun xotirada tarkibi quyidagicha bo‘lgan elementlarni olish kerak (4.6-rasm):