4-amaliy mashg’ulot

4.4. Daraxt “ko‘rigi” funksiyalari

4.5-rasmdagidek binar daraxt berilgan bo‘lsin:


4.5-rasm. 3 ta elemetdan iborat binar daraxt
Binar daraxtlari ko‘rigini uchta tamoyili mavjud. Ularni berilgan daraxt misolida ko‘rib chiqaylik:
1) Yuqoridan pastga ko‘rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq ko‘rikdan o‘tkaziladi): A, B, C ;
2) Chapdan o‘ngga: B, A, C ;
3) Quyidan yuqoriga (ildiz qism daraxtlardan keyin ko‘riladi): B, C, A .
Daraxt ko‘rigi ko‘pincha ikkinchi usul bilan, ya’ni tugunlarga kirish ularning kalit qiymatlarini o‘sish tartibida amalga oshiriladi.
4.5. Daraxt ko‘rigining rekursiv funksiyalari

1. 
   int pretrave(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 "<
pretrave(tree->left);
pretrave(tree->right);
}
return 0;
};

2. 
   int intrave(node *tree){
   

if(tree!=NULL) {
intrave(tree->left);
cout<info;
intrave(tree->right);
}
return 0;
};

3. 
   int postrave(node *tree){
   

if(tree!=NULL) {
postrave(tree->left);
postrave(tree->right);
cout<info;
}
return 0;
};
Daraxtning har bir tuguni 4.6-rasmdagidek oraliq (2, 3, 5, 7 elementlar) yoki terminal (daraxt “barg”i) (4, 9, 10, 11, 8, 6 elementlar) bo‘lishi mumkin.



4.6-rasm. Daraxtsimon tuzilma

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 8.7-rasmdagidek bir tomonga yo‘nalgan ro‘yhat hosil qiladi (chiqish darajasi bir bo‘ladi, ya’ni yagona shoxga ega), masalan:

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 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 "<

if (next->info>key) next=next->left;

else next=next->right;

}

cout<<"tuzilmada izlangan element yo‘q!!!"<

return 0;

}