Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering

daraxt tugunini o’chirish;

Daraxt tuguni o’chirilayotganda 3 ta holat bo’lishi mumkin:

1-holat. Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.

2-holat. Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.

3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtni topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday qismdaraxt har doim mavjud bo’ladi.

Bu chap qism daraxtning eng o’ng tomondagi tuguni;

o’ng qism daraxtning eng chap tuguni.

• 
  daraxt tugunini qidirish.
  

Mazkur amal (algoritm)ning vazifasi shundan iboratki, u berilgan qiymat bo’yicha daraxt tugunini izlab topishga yordam beradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yxat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shohga ega)

67. Дарахтда ўтиш амаллари: чап қисмдарахт -илдиз-ўнг қисм дарахт

• 
  Teskari o’tish: Chap qismdaraxt »» Ildiz »» O’ng qismdaraxt
  

Natijada hosil bo’lgan ro’yxat: {8, 4, 2, 9, 5, 10, 1, 6, 3, 7}



68. Дарахтда ўтиш амаллари: чап қисмдарахт - ўнг қисм дарахт-илдиз.

• 
  Oxiridan o’tish: Chap qismdaraxt »» O’ng qismdaraxt »» Ildiz
  

Natijada hosil bo’lgan ro’yxat: {8, 4, 9, 10, 5, 2, 6, 7, 3, 1}



69. Бинар дарахтдан тугунни ўчириш амалини тушунтириб беринг: ўчирилаётган тугун барг, оралиқ тугун, илдиз.

Daraxt tuguni o’chirilayotganda 3 ta holat bo’lishi mumkin:

• 
  1-holat. Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.
  
• 
  2-holat. Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
  
• 
  3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtni topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday qismdaraxt har doim mavjud bo’ladi. Bu
  
  • 
    chap qism daraxtning eng o’ng tomondagi tuguni;
    

o’ng qism daraxtning eng chap tuguni.



70. Бинар дарахтнинг рекурсив аниқланиши, унинг боғланган рўйхат орқали ифодаланишини мисоллар ёрдамида тушунтириб беринг.

Daraxt –bu tayanch rekursiv (o’z o’zi orqali aniqlangan) tuzilma hisoblanadi. Daraxtning aniqlanishi ikki qismga bo’linadi, birinchisi –rekursiyaning tugallanish shartining aniqlanishi, ikkinchisi esa rekursiyaning bajarilish mexanizmi.

bo’sh tuzilma daraxt hisoblanadi;

daraxt –bu ildiz va unga bog’langan bir nechta daraxtcha (qismdaraxt)lardir.

Yuqoridagilardan kelib chiqqan holda daraxt tuzilmasini Bekus –Naur shaklida quyidagicha ifodalash mumkin:

Daraxtni saqlash uchun zarur bo’lgan xotira o’lchami oldindan aniq bo’lmaydi, chunki, undan nechta tugun chiqishi ma’lum emas.