O„zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo„mitasi toshkent axborot texnologiyalari universiteti

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 
GetFlag
(){return Flag;} 
int 
main
() 
{ int n,key,s; node *tree=NULL,*next=NULL; 
cout<<"n="; cin>>n; int arr[n]; 
for(int i=0; i
        node *p=new node; 
        node *last=new node; 
        cin>>s; 
        p->info=s; 
        p->left=NULL; 

---

 
80 
        p->right=NULL; 
        if(i==0){tree=p; next=tree; continue; } 
        next=tree; 
while(1) 
        { last=next; 
        if(p->infoinfo)next=next->left; 
        else next=next->right; 
        if(next==NULL)break; } 
if(p->infoinfo)last->left=p; 
   else last->right=p;} 
       cout<
        cout<<"\nbinar daraxt:\n"; 
        vizual(tree,0); 
        AVLtree(tree); 
 if(GetFlag())  cout<<"ha,  muvozanatlangan  daraxt";  else  cout<<"yo’q, 
muvozanatlanmagan daraxt";cout<
       getch(); 
} 
 
Dastur natijasi 
 
      
 
4.12. Binar daraxtni vizuallashtirish 
 
Binar 
daraxtni 
ko‟rikdan  o‟tkazayotganda  biz  yuqorida  har  bir 

---

 
81 
 
tugunni o‟ngida va chapida turgan tugunlarni so‟z bilan ifodaladik. Lekin bu usul 
bir  muncha  noqulay.  Daraxtni  vizual  ko‟rinishda  ifodalash  uni  anglashning  juda 
qulay  usuli  hisoblanadi.  Daraxtni  vizuallashtirishning  grafik  ko‟rinishi  va  konsol 
oynasida  ifodalash  kabi  turlari  mavjud.  Shundan  konsol  oynasida  daraxtni 
vizuallashtirishni  ko‟rib  chiqamiz.  Bunda  sonlar  daraxt  shaklida  joylashtiriladi. 
Quyida bunday usulning dastur kodi keltirilgan. 
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); 
  } 
}
  
Dastur kodi quyidagi 4.10 a-rasmdagi daraxtni konsol ekranida 4.10 b-rasm 
ko‟rinishda ifodalaydi. 
 
  
 
                          a.                                                    b.  
4.10-rasm. a - binar daraxt; b - binar daraxtning ekranda namoyon bo‟lishi
 
 
Yuqorida  keltirilgan  bir  nechta  algoritmlarni  qo‟llab  bitta  misol  ko‟rib 
chiqamiz. 
 

---

 
82 
Misol: berilgan binar daraxtning balandligini aniqlang va muvozanatlang.