“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Daraxt o’zining quyidagi belgilari bilan tasniflanadi:

• Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
• Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojaat qilish mumkin;
• Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni orqaliq yoki terminal (barg) bo’lishi mumkin.

Def.2.
Daraxt bosqichlari soniga daraxt balandligi deyiladi.
Def.3.
Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.
0-bosqich
1- bosqich
2- bosqich
Chiqish darajalari.
3
1
2

Daraxtlar klassifikatsiyasi

1) Agar maksimal darajasi m bo’lsa, u holda bunday daraxt m-tartibli daraxt deyiladi;
2) Agar chiqish darajasi 0 yoki m bo’lsa, u holda to’liq m – tartibli daraxt deyiladi;
3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt binary daraxt deyiladi;
4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binary daraxt deyiladi.
Tugunlar orasidagi bog’liqlikni tavsiflash uchun yana quyidagicha atamadan foydaliniladi: Otao’g’il.
Eslatma
Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.

Daraxtlarni tavsiflash

Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.

Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.

12-mavzu bo’yicha nazorat savollari

• Rekursiya nima?
• Rekursiv obyekt, algoritm, funksiya tushunchasi.
• Rekursiv triada.
• Rekursiv algoritm samaradorligini aniqlash va oshirish yo’llari.
• Daraxt tushunchasi: balandligi, chiqish darajasi.
• Daraxt klassifikassiyasi.
• Daraxtlarni mantiqiy mavsiflash.