“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

 
4.10. Binar daraxt balandligi 
 
Binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. Binar 
daraxt balandligini aniqlash uchun uning har bir tuguni chap va o‟ng 
qismdaraxtlari balandliklari solishtiriladi va maksimal qiymat balandlik deb 
olinadi. Misol uchun quyidagi 4.9-rasmdagi daraxtning balandligi 2 ga teng. 
4.9-rasm. Binar daraxt balandligi 
Daraxt balandligini aniqlash dastur kodini keltiramiz. 
int height(node *tree){ 
int h1,h2; 
if (tree==NULL) return (-1); 
else { 
h1 = height(tree->left); 

---

78 
h2 = height(tree->right); 
if (h1>h2) return (1 + h1); 
else return (1 + h2); 
} 
} 
 
4.11. Binar daraxtni muvozanatlanganmi yoki yo‟qligini tekshirish 
 
Daraxtning balandligini aniqlashni o‟rganganimizdan keyin uning muvoza-
natlanganligini tekshirish mumkin. Binar daraxtning muvozanatlanganligini 
tekshirish uchun uning har bir tugunini har ikkala qismdaraxti balandliklarini 
hisoblab, farqlarini tekshirib ko‟rish kerak. Agar farq 
0
yoki 
1
ga teng bo‟lsa, bu 
muvozanatlangan daraxt hisoblanadi. Quyida binar daraxtni muvozanatlanganlikka 
tekshirishning rekursiv funksiyasini qo‟llovchi dastur keltirilgan. 
Dastur kodi 
#include  
#include  
using namespace std; 
class node{ 
public: int info; 
node *left;
node *right; 
}; 
int k=0,Flag=1; 
int 
height
(node *tree){ 
int h1,h2; 
if (tree==NULL) return (-1); 
else { 
h1 = height(tree->left); 
h2 = height(tree->right); 
if (h1>h2) return (1 + h1); 

---

79 
else return (1 + h2); 
} 
} 
void 
vizual
(node *tree,int l) 
{ int i; 
if(tree!=NULL) { 
vizual(tree->right,l+1); 
for (i=1; i<=l; i++) cout<<" "; 
cout<info<
vizual(tree->left,l+1); 
} 
} 
int 
AVLtree
 (node *tree){ 
int t; 
if (tree!=NULL){ 
t = height (tree->left) - height (tree->right); 
if ((t<-1) || (t>1)) { Flag = 0; return Flag; } 
AVLtree (tree->left); AVLtree (tree->right); 
} 
 } 
 int