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

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.
Daraxt bo’yicha o’tish – daraxt tugunlarini chop qilish.
Daraxt bo’yicha o’tish uchun rekursiyani qo’llash mumkin, chunki,
ixtiyoriy binar daraxt – bu rekursiv tuzilma hisoblanadi. 6-listingda daraxtni
ixtiyoriy tugunidan boshlab chop qilish funktsiyasi berilgan: birinchi chap
qismdaraxt, keyin o’ng qismdaraxt chop qilinadi.
Listing 6. Daraxt tugunlari mazmuni chiqarish
//ixtiyoriy tugunni chop qilish funktsiyasi
static void walk(const struct node * search_node)
{
if(node == NDLL) return;
walk(node->left);
printf("%d ", search_node->data);
walk(node->right);
}
//daraxtni ildizi bilan to’liq chop qilish
funktsiyasi
void walk2(const struct tree * my_tree)
{
walk(my_tree->root);
}
Daraxt bo’yicha o’tish uchun agar daraxtni o’tish vaqtida to’ldiriladigan
tugunlar ko’rsatkichlari massivi berilgan bo’lsa bitta funktsiyadan foydalanish
mumkin. Daraxt bo’yicha chap tugundan oxirigacha o’tish uchun funktsiyasida
tarkibli tsikl bajariladi. Qo’shimcha ko’rsatkichlar massivi butun daraxtni bitta
qadamda o’tishga yordam beradi. Bu massivda joriy ildiz tugunning ko’rsatkichi
saqlanadi.
Listing 8. Daraxt bo’yicha o’tishning rekursiv bo’lmagan tadbiqi
void traverse(const struct tree * search_tree)
{
struct node * stack[32];
int count;
struct node * search_node;
count = 0;
search_node = search_tree->root;
for(;;)
{
while(search_node != NOLL)
{
stack[count++] = search_node;
search_node = search_node->left;
}
if(count == 0) return ;
search_node = stack[-count];
printf("%d",search_node->data);
search_node = search_node->right;
}
}
73. Graflarning analitik ifodasi, graflarni qayta ishlashda qo’llaniladigan matritsalar.

• 
  Vaznli graflar uchun tugunlar orasida bog’lanish bor yoki yo’qligini oddiy ko’rsatish yetarli emas. Bunday graflarni qayta ishlash uchun xotirada har bir yoyning vazni saqlash talab etiladi, masalan, biletning narxi yoki yo’l uzunligini. Buning uchun vazn matritsasi qo’llaniladi.
  
•