|
Zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya
|
| bet | 26/47 | | Sana | 15.11.2023 | | Hajmi | 490,46 Kb. | | #99136 |
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:
Yuqoridan pastga ko‟rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq ko‟rikdan o‟tkaziladi): A, B, C ;
Chapdan o‟ngga: B, A, C ;
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.
Daraxt ko‟rigining rekursiv funksiyalari
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 "< o’ngida "<
pretrave(tree->left); pretrave(tree->right);
}
return 0;
};
int intrave(node *tree){ if(tree!=NULL) {
intrave(tree->left); cout<info; intrave(tree->right);
}
return 0;
};
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
Agar tugunning otasi yo‟q bo‟lsa, bu tugun ildiz hisoblanadi. Buni aniqlash uchun dastur kodini keltiramiz. Dasturda p izlanayotgan tugun.
if(p==tree) cout<<”bu tugun ildiz ekan”; else cout<<”bu tugun ildiz emas”;
Biz izlayotgan element daraxtda oraliq tugun ekanligini tekshirish uchun uning yoki o‟ng shoxi, yoki chap shoxi, yoki ikkalasiyam mavjudligini tekshirish kerak. Agar ikkala shoxi NULL dan farqli bo‟lsa, bu 2 ta farzandga ega oraliq tugun hisoblanadi, yoki ikkalasidan bittasi NULL ga teng bo‟lsa, bu tugun 1 ta farzandga ega oraliq tugun hisoblanadi. Berilgan p element daraxtning oraliq tugun ekanligini aniqlash dastur kodini keltiramiz.
if(p!=tree){
if((p->left!=NULL)&&(p->right!=NULL)) cout<<”bu tugun 2 ta farzandga ega oraliq tugun”;
else if((p->left!=NULL)||(p->right!=NULL) cout<<”bu 1 ta farzandga ega oraliq tugun”;
} else cout<<”bu tugun oraliq tugun emas”;
Biz izlayotgan tugun terminal tugunligini tekshirishni ko‟rib chiqamiz. Agar tugunning har ikkala shoxi NULL ga teng bo‟lsa, bu terminal tugun hisoblanadi. Dastur kodini keltiramiz.
if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal tugun”;
else cout<<”bu terminal tugun emas”;
|
| |
