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
v=p->right
,
v p
ning o‟ng tomonida turibdi,
t=p
va
s=v->left
, ya‟ni
s v
ning chapida turibdi. Endi to
s NULL
bo‟lguncha chapga ketamiz, undan 1 ta orqada
v
va
v
dan 1 ta orqada
t
keladi. Mana endi biz
p
ning o‟rniga
v
olib borib qo‟yishimiz mumkin.
7.
Agar
t NULL
bo‟lmasa va
t p
ga teng bo‟lmasa (agar
p
ning bitta farzandi
mavjud bo‟lsa, uning o‟rniga keladigan tugunni izlashga xojat yo‟q, chunki uning
o‟sha farzandi aynan
p
ning o‟rniga joylashadi. Agar o‟chirilayotgan
p
tugunning 2
ta farzandi mavjud bo‟lsa, shu shart bajariladi), u holda,
p
ning o‟rniga ketayotgan
v
tugunning farzandi (agar u mavjud bo‟lsa)
v
ning otasi bo‟lmish
t
ga meros
qoldiriladi, ya‟ni
v->right v
ning o‟rniga keladi.
t->left=v->right
. Endigi ish
p
ning
har ikkala tomonidagi tugunlarni
v
ga o‟zlashtiramiz.
8.
Agar
t p
ga teng bo‟lsa (ya‟ni p o‟chayotgan tugunning o‟rniga o‟zining
88
farzandi kelayotgan bo‟lsa),
p
ning chapidagi tugunni
v
ning chapiga
o‟zlashtiramiz.
9.
Mana
p
tugunning o‟rniga
v
tugun keldi. Endigi vazifa
v
ni
p
ning otasi
bilan ulash kerak. Buning uchun aniqlash kerak –
p
tugunning otasi
q NULL
ga
teng emasmi? Agar
q NULL
bo‟lsa, biz daraxt ildizini o‟chirgan bo‟lamiz. Bu
holda daraxt ildizi ko‟rsatkichi
tree
ni
v
ga tenglab qo‟yamiz. Aks holda, 10-
qadamga o‟tamiz.
10.
p
tugun otasi
q
tugunning qaysi tomonida turgan edi? Agar
p q
ning
chapida turgan bo‟lsa,
p
ning o‟rniga, ya‟ni
q->left
ga
v
ni joylaymiz, aks holda
q-
>right
ga
v
ni joylaymiz.
11.
p
tugun joylashgan xotira yacheykasini tozalab qo‟yamiz va algoritm
yakunlanadi.
Dastur kodi
#include
#include
using namespace std;
class node{
public: int info;
node *left;
node *right;
};
int intrave(node *tree){
if (tree!=NULL){int a=0, b=0;
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;
}
89
node *del(node *tree,int key){
node *p=new node;
node *next=tree;
node *q=NULL;
while(next!=NULL)
{
if
(next->info==key){cout<<"Binar
daraxtda
"<
Mavjud"<
p=next;break; }
if (next->info>key){ q=next; next=next->left; }
else {q=next;next=next->right;}
}
if(next==NULL) cout<<"tuzilmada izlangan element yo
‟
q!!!"<
node *v=NULL,*t=NULL,*s=NULL;
if(p->left==NULL) v=p->right;
else if(p->right==NULL) v=p->left;
if((p->left!=NULL)&&(p->right!=NULL)){t=p; v=p->right; s=v->left;}
while(s!=NULL){
t=v;
v=s;
s=v->left;
}
if((t!=NULL)&&(t!=p)){
t->left=v->right;
v->right=p->right;
v->left=p->left;
}
if(t==p) v->left=p->left;
if(q==NULL){
cout<info<<" ildiz\n";
tree=v;
90
delete(p);
return tree;
}
if(p==q->left)
q->left=v;
else q->right=v;
delete(p); // o’chirilgan element joylashgan xotira yacheykasini tozalash
return tree;
}
int main()
{ int n,key,s; node *tree=NULL,*next=NULL;
cout<<"n="; cin>>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);
91
cout<<"delete qilinadigan elementni kiriting \n";
cout<<"key="; cin>>key;
tree=del(tree,key);
intrave(tree);
getch();
}
