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

void reverse(struct tree *p) 
{ 
 
struct tree * temp; 
 
 
 
if(p) 
 
{ 
 
 
if(p->left  &&  p->right)  
 
 
{ 
 
 
 
temp = p->left; 
 
 
 
p->left = p->right; 
 
 
 
p->right = temp; 
 
 
 
reverse(p->left); 
 
 
 
reverse(p->right); 
 
 
} 
 
 
else  if  (p->left  &&  !p->right)  reverse(p-
>left); 
 
else  if  (!p->left  &&    p->right)  reverse(p-
>right); 
 
} 
} 
 
6.6. Binar daraxtda tugunni qidirish 
Binar daraxtda tugunni uning qiymati bo’yicha qidirish uchun 4-listingda 
berilgan lookup funktsiyasi qo’llaniladi: 
Listing 4. Daraxtdan tugunni qidirish – C tilida rekursiv tadbiqi 
int lookup(struct node* node, int target) 
{ 
if (node == NULL) 

---

105 
 
{ 
return(0); 
} 
else 
{ 
if (target == node->data) return(1); 
else 
{ 
if (target < node->data) return(lookup(node->left, 
target)); 
else return(lookup(node->right, target)); 
} 
} 
} 
 
6.7. Binar daraxt kengligi 
Daraxtning  kengligi  deganda  bitta  darajadagi  (bir  xil  balandlikda 
joylashgan) tugunlarning maksimal soni tushuniladi. Daraxt kengligini aniqlash 
uchun  yuqorida  qarab  chiqilgan  daraxt  balandligini  aniqlash  algoritmiga 
oddiygina hisoblagini qo’shish yetarli bo’ladi. 
Listing 5. Daraxt kengligini aniqlash – C tilida rekursiv aniqlanishi 
int getMaxWidth(struct node* root) 
{ 
 
int maxWdth = 0; 
 
int i; 
 
int width = 0 ; 
 
int h = height(root); 
 
for( i = 1; i< h; i++) 
 
{ 

---

106 
 
 
 
width =   getWidth(root, i); 
 
 
if(width > maxWdth) 
 
 
 
maxWdth  = width; 
 
} 
 
return maxWdth; 
} 
 
int getWidth(struct node* root,int level) 
{ 
 
if (!root) return 0; 
 
if (level == 1) return 1; 
 
else if (level > 1) 
return 
getWidth(root->left, 
level-1) 
+  
getWidth(root->right, level-1); 
getWidth(root->right, level-1); 
} 
 
6.8. Binar daraxtdagi tugunlar soni 
Binar  daraxtning  tugunlar  sonini  hisoblash  uchun  ham  rekursiyadan 
foydalanish mumkin.  
Listing  6.  Daraxtdagi  tugunlar  sonini  hisoblash  –  C  tilida  rekursiv 
aniqlanishi 
int size(struct node* node)  
{ 
 
if (node==NULL)  
 
{ 
 
 
return(0); 
 
}  
 
else  

---

107 
 
 
{ 
 
return(size(node->left)  +  1  +  size(node-
>right)); 
 
} 
} 
 
6.9. Binar daraxtlarni taqqoslash 
Ikkita  turli  binar  daraxtlarning  mosligini  aniqlash  uchun  7-listingdagi 
algoritmni qo’llash mumkin. 
Listing 7. Binar daraxtlarni taqqoslash – C tilida rekursiv aniqlanishi 
int sameTree(struct node* a, struct node* b)  
{ 
 
if (a==NULL && b==NULL) return(true); 
 
else if (a!=NULL && b!=NULL)  
 
{ 
 
 
return( 
 
 
 
a->data == b->data && 
 
 
 
sameTree(a->left, b->left) && 
 
 
 
sameTree(a->right, b->right) 
 
 
 
); 
 
} 
 
else return(false); 
} 
 
Xulosa 
Ushbu  mavzudagi  algoritmlarning  Si  va  Python  tillaridagi  dasturlar 
(algoritmlar)  kodi  tree_operations.c  va  tree_operations.py  fayllarida  (kitobning 
ilovasida) berilgan.  

---

108 
 
Ushbu mavzuda binar daraxtlar klassifikatsiyasi va ular ustida bajariladigan 
muhim  amallar:  balandlikni  aniqlash,  kenglikni  aniqlash,  daraxtni  tasvirlash  va 
berilgan elementni qidirish kabi algoritmlar qarab chiqildi. Shuningdek Xaffman 
algoritmining  kengaytirilgan  daraxtni  qurish  va  axborotlarni  shifrlashda 
qo’llanishi o’rganib chiqildi.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

---

109 
 
7-qism. Binar qidiruv daraxti (BST) 
 
Ushbu  mavzuda  ikkilik  daraxtlarning  yana  bir  ko’rinishi:  binar  qidiruv 
daraxti xususiyatlari bilan tanishib chiqamiz. Odatdagidek, ushbu tuzilma ustida 
bajariladigan turli amallar: tugun qo’shish va o’chirish, eng katta va eng kichik 
qiymatlarni  qidirish  algoritmlarini  nazariy  jihatdan  o’rganib,  ularning  Si  va 
Python dasturlash tillaridagi amaliy tadbiqlarini qarab chiqamiz.