|
int delete(struct tree * search_tree, int ** item)
{
struct node ** q,*z;
q=&search_tree->root;
z=search_tree->root;
//o’chiriladigan elementni qidirish
for(;;)
{
if(z == NULL) return 0;
else if(item == (int **)z->data) break;
else if(item > (int **)z->data)
{
q = &z->right;
z = z->right;
}
else
{
q = &z->left;
z = z->left;
}
}
// elementni bevosita o’chirish
116
if(z->right == NULL) *q = z->left;
else
{
struct node * y = z->right;
if(y->left == NULL)
{
y->left = z->left;
*q-y;
}
else
{
struct node * x=y->left;
while(x->left != NULL)
{
y = x;
x = y->left;
}
y->left = x->right;
x->left = z->left;
x->right = z->right;
*q=x;
}
}
search_tree->count --;
free(z);
return 1;
}
117
7.4. 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)
{
118
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;
}
}
8-listingdaga stek qo’llanilgan, real holatda stek uchun dinamik xotira
ajratiladi.
7.5. Daraxtni o’chirish
Bu bo’limda daraxtni barglardan boshlab ildiz tugungacha to’liq o’chirish
funktsiyasi bilan tanishamiz.
Listing 9. Daraxtni o’chirish funktsiyasi
//daraxtning alohida tuguni va
//uning avlodlarini o’chirish funktsiyasi
static void destroy(struct node * search_node)
119
{
if(search_node == NOLL) return;
destroy(search_node->left);
destroy(search_node->right);
free(search_node);
}
//daraxtni to’liq o’chirish funktsiyasi
void destroy(struct tree * search_tree)
{
destroy(search_tree->root);
free(search_tree);
}
7.6. Binar qidiruv daraxtida minimum va maksimumlarni topish
10-listingda daraxtdagi eng katta (maksimum) va eng kichik (minimum)
qiymatli tugunlarni qidirish uchun ikkita funktsiya berilgan. Eng kichik qiymatni
ildizdan chap qism daraxtdan, eng katta qiymatni esa o’ng qism daraxtdan qidirish
kerak.
Listing 10. Minimal va maksimal qiymatlarni qidirish funktsiyasi
struct
node
*
tree_minimum(struct
tree
*
search_tree)
{
struct node * search_node;
search_node = search_tree->root;
while (search_node->left != NULL)
search_node = search_node->left;
return search_node;
}
120
struct
node
*
tree_maximum(struct
tree
*
search_tree)
{
struct node * search_node;
search_node = search_tree->root;
while (search_node->right != NULL)
search_node = search_node->right;
return search_node;
}
7.7. Ikkilik daraxtning turini aniqlash
Berilgan binar daraxtning binar qidiruv daraxt ekanligini aniqlash uchun
11-listingda berilgan funktsiyadan foydalanish.
Listing 11. Binar daraxtning turini aniqlash
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(struct node* node, int min, int max)
{
if (node==NULL) return(true);
if (node->datadata>max) return(false);
return (
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}
121
7.8. Algoritmlarning amaliy tadbiqi
C tilidagi tadbiqi
Biz boshida binar daraxtga 10 ta element qo’shgan edik, buning uchun
uning barcha atributlarini tabiiy ravishda kuzatib bordik – ya’ni, masalan,
daraxtga element qo’shish uchun uning joyini binar algoritm bo’yicha aniqlab
oldik. Keyin daraxt bo’yicha o’tish, daraxtni chop qilish, elementni o’chirish,
daraxtni qayta chop qilish, daraxtni to’liq o’chirish kabi amallarni o’rganib
chiqdik. Binar qidiruv daraxti uchun yuqoridagi barcha amallarni o’zida qamrab
olgan C tilidagi dastur kodi quyida berilgan:
Do'stlaringiz bilan baham: | 
