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

terminal tugun
 
hisoblanadi. Dastur kodini keltiramiz. 
if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal 
tugun”; 
else cout<<”bu terminal tugun emas”;
 
4.6. Binar daraxt bo
‟
yicha qidiruv funksiyasi 
Mazkur funksiyaning vazifasi shundan iboratki, u berilgan kalit bo‟yicha 
daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi 
daraxt tuzilishiga bog‟liq bo‟ladi. Haqiqatdan, agar elementlar daraxtga kalit 
qiymatlari o‟sish (kamayish) tartibida kelib tushgan bo‟lsa, u holda daraxt 4.7-
rasmdagidek bir tomonga yo‟nalgan ro‟yhat hosil qiladi (chiqish darajasi bir 
bo‟ladi, ya‟ni yagona shoxga ega), masalan: 

---

71 
4.7-rasm. Bir tomonlama yo‟naltirilgan binar daraxt tuzilishi
Bu holda daraxtda qidiruv vaqti, bir tomonlama yo‟naltirilgan ro‟yhatdagi 
kabi bo‟lib, o‟rtacha qarab chiqishlar soni N/2 bo‟ladi. Agar daraxt 
muvozanatlangan bo‟lsa, u holda qidiruv eng samarali natija beradi. Bu holda 
qidiruv 
N
2
log
dan ko‟p bo‟lmagan elementlarni ko‟rib chiqadi. 
Qidiruv funksiyasini ko‟rib chiqamiz. 
search
fuksiyasi daraxtdan 
key
kalitga 
mos elementning adresini aniqlaydi. 
int search(node *tree, int key){ 
node *next; next=tree; 
while(next!=NULL) 
{ if (next->info==key){cout<<"Binar daraxtda "<
return next; }
if (next->info>key) next=next->left; 
else next=next->right;
} 
cout<<"tuzilmada izlangan element yo
’
q!!!"<
return 0; 
} 
 
4.7. Daraxtga yangi element qo