Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

#include < stdio.h> 
#include < stdlib.h> 
int count; 
struct node 
 { 
  
int data; 
  
struct node * left; 
   struct node * right; 
 }; 
struct tree 
 { 
struct node * root; 
   int count; 
 }; 
 struct tree * tree_create(void) 
 { 
struct tree * new_tree = malloc(sizeof * new_tree); 
if (new_tree == NULL) return NULL; 
  
new_tree->root = NULL; 
  
new_tree->count = 0; 

---

122 
 
  
return new_tree; 
 } 
int bin_search(const struct tree * search_tree, int 
item) 
 { 
const struct node * search_node; 
   search_node = search_tree->root; 
 for(;;) 
{ 
 
if (search_node == NULL) return 0; 
 
else if (item == search_node->data) return 1; 
 
else if (item > search_node->data) search_node 
= search_node->right; 
else search_node = search_node->left;   
} 
 } 
 int insert(struct tree * search_tree, int item) 
 { 
  
struct node * search_node, **new; 
  
new = &search_tree->root; 
  
search_node = search_tree->root; 
  
for(;;) 
  
{ 
  
 
if(search_node == NULL) 
  
 
{ 
 
search_node 
= 
*new 
= 
malloc(sizeof 
* 
search_node); 
 
 
if(search_node != NULL) 
 
 
{ 

---

123 
 
 
 
search_node->data = item; 
 
 
search_node->left 
= 
search_node-
>right=NULL; 
 
 
search_tree->count++; 
 
 
return 1; 
 
 
} 
 
 
else return 0; 
  
 
} 
else if(item == search_node->data) return 2; 
 else if(item > search_node->data) 
     { 
    new = &search_node->right; 
search_node = search_node->right; 
 
} 
else 
{ 
 
new = &search_node->left; 
 
search_node = search_node->left; 
 
} 
} 
 } 
 int delete(struct tree * search_tree, int ** item) 
 { 
  
struct node ** q,*z; 
  
q=&search_tree->root; 
  
z=search_tree->root; 
  
for(;;) 
  
{ 
  
 
if(z == NULL) return 0; 

---

124 
 
  
 
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; 
  
 
} 
  
} 
 
 
 
// tugunni o’chirish 
  
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; 

---

125 
 
  
 
 
} 
  
 
 
y->left = x->right; 
  
 
 
x->left = z->left; 
  
 
 
x->right = z->right; 
  
 
 
*q=x; 
  
 
} 
  
} 
  
  
search_tree->count --; 
  
free(z); 
  
return 1; 
 } 
void traverse(struct tree * search_tree) 
 { 
  
struct node * stack[search_tree->count]; 
  
int count; 
  
struct node * search_node; 
  
count = 0; 
   search_node = search_tree->root; 
 
for(;;) 
  
{ 
  
 
while(search_node != NULL) 
  
 
{ 
  
 
 
stack[count++] = search_node; 
  
 
 
search_node = search_node->left; 
  
 
} 
  
 
if(count == 0) return ; 
  
 
search_node = stack[--count]; 
  
 
printf("%d\n",search_node->data); 

---

126 
 
  
 
search_node = search_node->right; 
  
} 
 } 
static void destroy(struct node * search_node) 
 { 
  
if(search_node == NULL) return; 
  
destroy(search_node->left); 
  
destroy(search_node->right); 
  
free(search_node); 
 }  
void bin_destroy(struct tree * search_tree) 
 { 
  
destroy(search_tree->root); 
  
free(search_tree); 
 } 
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; 
 } 
struct 
node 
* 
tree_maximum(struct 
tree 
* 
search_tree) 
 { 
  
struct node * search_node; 
   search_node = search_tree->root; 

---

127 
 
  
while (search_node->right != NULL) 
  
search_node = search_node->right; 
  
return search_node; 
 } 
int  main() 
 { 
 
struct tree * my_tree = tree_create(); 
  
int res = insert(my_tree, 100); 
  
res = insert(my_tree, 10); 
  
res = insert(my_tree, 4); 
  
res = insert(my_tree, 13); 
  
res = insert(my_tree, 27); 
  
res = insert(my_tree, 3); 
  
res = insert(my_tree, 31); 
  
res = insert(my_tree, 7); 
  
res = insert(my_tree, 12); 
  
res = insert(my_tree, 8); 
 
my_tree->count = 10; 
  
traverse(my_tree); 
struct node * tree_min = tree_minimum(my_tree); 
  
printf("\n%d\n\n", tree_min->data); 
  
struct 
node 
* 
tree_max 
= 
tree_maximum(my_tree); 
  
printf("\n%d\n\n", tree_max->data); 
  
res = delete(my_tree, 31); 
  
traverse(my_tree); 
  
bin_destroy(my_tree); 
 
return 0 ; 
} 

---

128 
 
Python tilidagi tadbiqi 
class node: 
def 
__init__(self, 
data=None, 
left=None, 
right=None): 
         self.data   = data 
         self.left   = left 
         self.right  = right 
     def __str__(self): 
        return 'Node ['+str(self.data)+']' 
class Tree: 
     def __init__(self): 
         self.root = None 
         self.count = 0 
     def insert(self,data): 
         if self.root == None: 
             self.root = node(data,None,None) 
             return 
         root = self.root         
         while (root != None): 
             if (data < root.data): 
                 if root.left == None: 
              root.left = node(data, None, None) 
                     return 
                 else: 
                   root = root.left 
             else: 
                 if root.right == None: 
              root.right = node(data, None,None) 
                    return 

---

129 
 
                 else: 
              root = root.right 
     def traverse(self,node): 
         if node == None: 
             return 
         print node.data 
         if node.left: 
           self.traverse(node.left) 
         if node.right: 
           self.traverse(node.right) 
t  = Tree() 
 res = t.insert( 100) 
 res = t.insert( 10) 
 res = t.insert( 4) 
 res = t.insert( 13) 
 res = t.insert( 27) 
 res = t.insert( 3) 
 res = t.insert( 31) 
 res = t.insert( 7) 
 res = t.insert( 12) 
 res = t.insert( 8) 
 t.traverse(t.root) 
C tilidagi dastur kodi Python tilidagiga nisbatan ko’p funktsionallikka ega. 
C  tilidagi  dasturda  birinchi  10  ta  elementdan  iborat  binar  qidiruv  daraxti  hosil 
qilinadi, keyin daraxt chop etiladi, undan bitta tugunni o’chirish amali bajariladi. 
Hosil  bo’lgan  yangi  daraxt  qayta  chop  etiladi.  Bunday  chop  etishdan  maqsad 
o’chirish amali qanday bajarilganligini kuzatish uchun amalga oshiriladi. Oxirida 
daraxt to’liq o’chiriladi, ya’ni xotira bo’shatiladi. Python tilidagi dasturda faqat 
10  ta  tugundan  iborat  binar  daraxt  hosil  qilish  va  uni  chop  etish  funktsiyalari 

---

130 
 
berilgan.  Qolgan  algoritmlar  keltirilmagan,  bu  algoritmlarning  Python  tilidagi 
tadbiqini mustaqil ravishda C tilidagi dastur kodi namunasi asosida ishlab chiqish 
mumkin.  
Ushbu mavzuda eng mashhur ma’lumotlar tuzilmasidan biri binar qidiruv 
daraxti  bilan  ishlash  bo’yicha  asosiy  ma’lumotlar  taqdim  etildi.  Nazariy 
ma’lumotlar bilan birgalikda o’rganilgan algoritmlarning C tilidagi to’liq tadbiqi 
keltrildi.  
Quyidagi listingda bst-daraxtning Python tilidagi tadbiqi keltirilgan. Ushbu 
dastur binar qidiruv daraxti ustida bajariladigan standart amallar: daraxtni hosil 
qilish, tugun qo’shish, tugunni o’chirish, daraxtning haqiqiyligini tekshirish kabi 
amallarni  bajarishga  mo’ljallangan.  Dastur  stsenariysi  bo’yicha  binar  qidiruv 
daraxti 50 ta tugundan tashkil topadi, uni ekranga chiqaradi, keyin ildiz tugunni 
o’chiradi va hosil bo’lgan yangi binar qidiruv daraxtini ekranga chop qiladi: