92
8-amaliy mashg’ulot
Mavzu: Daraxtsimon ko’rinishdagi ma’lumotlar tuzilmasini tadqiq qilish.
Ikkilik daraxtsimon ma’lumotlar tuzilmasini tadqiq qilish.
Ishdan maqsad: Talabalar
daraxtsimon tuzilmalar, binar daraxtlarni e’lon qilish,
uning ustida amallar bajarish algoritmlarini tadqiq qilishlari va o‘rganishlari kerak,
bu algoritmlarning dasturiy realizatsiyasini amalga oshirish ko‘nikmasiga ega
bo‘lishlari kerak.
Qo‘yilgan masala: Har bir
talaba topshiriq varianti olib,
undagi masalaning
qo‘yilishiga mos binar daraxtlarni tadqiq qilishga oid
dasturni ishlab chiqishlari
kerak.
Ishning vazifasi:
Binar daraxtlarni tashkil qilish. Ular
ustida amallar
Qidiruv binar daraxti.
Tugunlarni qo’shish. Daraxt balandligi aniqlash.
Daraxt ko‘ruvi, burash algoritmlari
Ish tartibi:
Amaliy mashg’ulot nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Nazariy qism.
8.1. Daraxt ko‘rinishidagi ma’lumotlar tuzilmasi haqida umumiy
tushunchalar.
Uzellar (elementlar) va ularning munosabatlaridan iborat elementlar to‘plamining
ierarxik tuzilmasiga daraxtsimon ma’lumotlar tuzilmasi deyiladi.
Daraxt – bu shunday chiziqsiz bog‘langan ma’lumotlar
tuzilmasiki,
u quyidagi
belgilari bilan tavsiflanadi:
- daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo‘q.
93
Bu element daraxt ildizi deyiladi;
- daraxtda ixtiyoriy element chekli sondagi ko‘rsatkichlar
yordamida boshqa
tugunlarga
murojaat qilishi mumkin;
- daraxtning har bir elementi faqatgina o‘zidan oldingi kelgan bitta element bilan
bog‘langan.