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

 
Dastur kodi 
#include  
#include  
using namespace std; 
class 
node
{ 
      public: int info; 
      node *left;       
      node *right; 
      }; 
     int k=0; 
int 
intrave
(node *tree){ 
    if (tree!=NULL){int a=NULL, b=NULL;   
    if (tree->left!=NULL){ a=tree->left->info; }  
    if (tree->right!=NULL){ b=tree->right->info;  } 
    cout<info<<"--chapida=>"<"<
    intrave(tree->left); 
    intrave(tree->right);   }  
    return 0; 
    } 
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); 
   else  return (1 + h2); 
  } 
} 

---

 
83 
 
int 
create_arr
(node *tree,int *arr){ 
    if(!tree) return 0; 
    else{ 
         create_arr(tree->left,arr); 
         arr[k++]=tree->info; 
         create_arr(tree->right,arr); 
         } 
    } 
node 
*new_tree
(int *arr, int start, int end) 
{ 
    if(start>end) return NULL; 
    else  { 
        int mid=(start+end)/2;   
        node *tree=new node; 
        tree->info=arr[mid];  
        tree->left=new_tree(arr,start,mid-1);  
        tree->right=new_tree(arr,mid+1,end); 
        return tree;   
    } 
} 
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 
main
() 

---

 
84 
{ 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; 
        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<
        intrave(tree); 
        cout<<"\nya'ni\n"; 
        vizual(tree,0); 
        int h=height(tree); 
        cout<<"balandligi="<
        create_arr(tree,arr); 
       for(int i=0;i
       tree=new_tree(arr,0,k-1); 
       vizual(tree,0); 
       getch(); 
}      

---

 
85 
 
Dastur natijasi 
 
 
Ishni bajarishga namuna 
 
Topshiriq variantlariga o‟xshash bitta misolning algoritmi va to‟liq dasturini 
ko‟rib chiqaylik. 
Misol:  berilgan  binar  daraxtdan  ko‟rsatilgan 
key
  kalitga  mos  tugunni 
o‟chirish dasturini tuzing.  
Algoritm 
Asosiy dastur tanasi - 
int main()
 
1.
 
i=0;  n
  –  daraxtga  kiritiladigan  elementlar  sonini  aniqlash.  Daraxt  ildizi 
ko‟rsatkichi 
tree=NULL
. 
Next
  yangi  elementni  joylashtiradigan  shoxga  o‟tishda 
ishlatiladi va 
last next
 dan 1 qadam orqada yuradi.  
2.
 
Agar 
i
  bo‟lsa,  daraxtga  kiritiladigan  navbatdagi  elementga  qiymat 
kiritish va uni yangi 
p
 element 
info
 maydoniga yozish, 
left
 va 
right
 maydonlarga 
NULL
 yozish. Aks holda 8-qadamga o‟tish. 
3.
 
Agar 
tree=NULL
 bo‟lsa, 
p
 ni 
daraxt  ildizi  qilish,  ya‟ni 
tree=p
  va 

---

 
86 
next=last=p
.    
4.
 
Agar 
p->info  next->info
  dan  kichik  bo‟lsa,  chap  shoxga  o‟tish  kerak, 
ya‟ni 
last=next
 va 
next=next->left
, aks holda o‟ng shoxga o‟tamiz, ya‟ni 
last=next
 
va 
next=next->right
.  
5.
 
Agar 
next=NULL
 bo‟lsa, 6-qadamga o‟tish, aks holda 4-qadamga o‟tish. 
6.
 
Agar 
p->infoinfo
 bo‟lsa, 
last->left=p
, aks holda 
last->right=p
. 
7.
 
i++
, 2-qadamga o‟tish. 
8.
 
intrave(tree)
 funksiyasini ishlatish. 
9.
 
Key
  kalitga  mos  elementni  daraxtdan  o‟chiradigan 
del(tree,key)
 
funksiyasini ishlatish. 
10.
 
Natijaviy  daraxtni  ko‟rikdan  o‟tkazish  uchun 
intrave(tree)
  funksiyasini 
ishlatish va algoritmni yakunlash. 
intrave(tree)
 funksiyasining ishlash algoritmi 
1.
 
Agar  funksiyaning  kirishiga  berilgan  tugun  NULL  bo‟lmasa,  2-qadamga 
o‟tish, aks holda funksiya chaqirilgan joyga qaytib borish. 
2.
 
Agar tugunning chap shoxi tuguni NULL bo‟lmasa, uning info maydonini 
yangi butun toifali a ga o‟zlashtirish, aks holda a=0. 
3.
 
Agar tugunning o‟ng shoxi tuguni NULL bo‟lmasa, uning info maydonini 
yangi butun toifali b ga o‟zlashtirish, aks holda b=0. 
4.
 
Ekranga  tugunning  info  maydoni  qiymatini,  tugunning  chapidagi  a  va 
o‟ngidagi b ni chiqaramiz. 
5.
 
Endi  shu  intrave()  funksiyasining  kirishiga  joriy  tugunning  chap  shoxi 
tugunini  berib  chaqiramiz,  ya‟ni  yuqoridagi  4  ta  amalni  joriy  tugunning  chap 
shoxidagi tugun ustida bajaramiz. 
6.
 
Endi  shu  intrave()  funksiyasining  kirishiga  joriy  tugunning  o‟ng  shoxi 
tugunini  berib  chaqiramiz,  ya‟ni  yuqoridagi  4  ta  amalni  joriy  tugunning  o‟ng 
shoxidagi tugun ustida bajaramiz. 
del() funksiyasining ishlash algoritmi 
Funksiyaning kirishiga daraxt ildizi ko‟rsatkichi 
tree
 va o‟chirilishi kerak  
 

---

 
87 
 
bo‟lgan tugunning 
info
 maydoni qiymati 
key
 beriladi. Daraxtning 
key
 kalitli 
tugunini terminal tugungacha izlaymiz. Dastlab 
next=tree
. 
1.
 
Toki 
next  NULL
  bo‟lguncha,  agar 
next
  tugunning 
info
  maydoni 
key
  ga 
teng bo‟lsa, izlayotgan tugunni topdik va uning adresini 
p
 ga joylaymiz va          4-
qadamga o‟tamiz. Agar 
next NULL
 bo‟lsa, 3-qadamga o‟tamiz. 
2.
 
Agar 
key
 
next
  ning 
info
sidan  kichik  bo‟lsa,  joriy  tugunning  chap 
tomonidagi  tugunga  o‟tamiz,  ya‟ni 
next=next->left
,  aks  holda  o‟ng  shoxdagi 
tugunga o‟tamiz. 1-qadamga qaytamiz. 
3.
 
Agar 
next  NULL
  ga  teng  bo‟lsa,  biz  izlagan  tugun  tuzilmada  yo‟q. 
Tugunni  o‟chirish  algoritmi  tugaydi  va  dastur  bajarilishi  o‟chirish  funksiyasi 
chaqirilgan joyga qaytib boradi. 
4.
 
Agar 
p
 o‟chirilayotgan tugunning chap tomonida tugun yo‟q bo‟lsa (ya‟ni 
p->left=NULL bo‟lsa), uning o‟ng tomonidagi tugun adresini 
v
 ga o‟zlashtiramiz. 
5.
 
Agar 
p
 o‟chirilayotgan tugunning o‟ng tomonida tugun yo‟q bo‟lsa, uning 
chap tomonidagi tugun adresini 
v
 ga o‟zlashtiramiz. 
6.
 
Agar 
p
  o‟chirilayotgan  tugunning  chapi  va  o‟ngida  element  mavjud 
bo‟lsa, bu tugunning o‟rniga da‟vo qiladigan tugunni topish uchun shu tugundan 1 
marta  o‟ngga  va  oxirigacha  chap  shox  tuguniga  o‟tamiz.  Ya‟ni