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;
}
