Malumotlar tuzilmasi va algoritmlash

OʻZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

MALUMOTLAR TUZILMASI VA ALGORITMLASH

4-Amaliy mashg`ulot
Bajardi: Sharofiddinov Shahzod

Toshkent 2022

№4- AMALIY ISH. DARAXTSIMON MAʻLUMOTLAR TUZILMALARI. IKKILIK (BINAR) DARAXTI


Ishdan maqsad: Daraxtsimon ma’lumotlar tuzilmalarini, shu jumladan ikkilik qidiruv daraxtlarini o'rganish. Daraxtsimon ma’lumotlar tuzilmalari bilan ishlash bo’yicha amaliy ko’nikmaga ega bo'lish. Daraxtsimon ma’lumotlar tuzilmalari ustida amallar bajarishni o’rganish.
Qo’yilgan masala: Amaliy ishi uchun topshiriqqa muvofiq dastur tuzing.
Ish tartibi:

• 
  Laboratoriya ishi nazariy ma’lumotlarini o’rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ (yoki ixtiyoriy) dasturlash tilida dasturni tuzish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Daraxt - bu qirralar bilan bog'langan tugunlarni o'zida aks ettiruvchi ma’lumotlar tuzilmasidir. Daraxt - bu dasturlash fanida eng ko'p qo'llaniladigan ma'lumotlar tuzilmalaridan biri bo'lib, daraxt tuzilishini bog'langan tugunlar to'plami sifatida aks ettiradi. Bu tsikllarni o'z ichiga olmaydigan bog'langan grafdir. Ko’pgina manbalarda daraxt sifatida grafning qirralari yo'naltirilmaganligi sharti ham qo'shiladi.

Daraxtlar chiziqsiz ma’lumotlar tuzilmalaridir. Ular ma'lumotlarni chiziqli tarzda saqlamaydilar, lekin ularni ierarxik tarzda tartibga soladilar. Daraxt - bu tugunlar deb ataladigan ob'ektlar to'plami. Tugunlar qirralar bilan bog'langan bo’ladi. Har bir tugun qiymat yoki biror ma'lumotni o’zida saqlaydi. Har bir tugun voris tugunga ega bo’lishi yoki bo'lmasligi mumkin.
Daraxtning yagona cheklovi shundaki, har bir tugun ko'pi bilan bitta ajdod tugunga ega bo'lishi mumkin. Eng yuqori tugunning ajdodi bo’lmaydi. Ushbu tugun "ildiz" deb ataladi.
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.
  

1-rasm. Daraxtsimon ma’lumotlar tuzilmasi.

Daraxt bosqichlari soniga daraxt balandligi deyiladi. Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.

2-rasm. Daraxt bosqichlari.

Daraxtlar chiqish darajasi bo’yicha klassifikasiya qilinadi.

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 deyiladi;
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.

Tugunlar orasidagi bog’liqlikni tavsiflash uchun yana quyidagicha atamadan foydalaniladi: otao’g’il.

Mantiqiy tasvirlanishda daraxtlar bog’langan ro’yxatlar ko’rinishida ifodalanadi. Bunda ro’yxat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi informasion maydonga xamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.

3-rasm. Daraxtsimon ma’lumotlar tuzilmasini mantiqiy tasvirlash.

Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tugun bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.

Umumiy holda binary daraxt har bir element 4ta maydonga ega yozuv hisoblanadi.

Qidiruv Binar daraxtda