Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

70. Binar daraxtning rekursiv aniqlanishi, uning bog’langan ro’yxat orqali ifodalanishini misollar yordamida tushuntirib bering.
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;}}
http://fayllar.org