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



Yüklə 1,33 Mb.
Pdf görüntüsü
səhifə31/56
tarix08.09.2023
ölçüsü1,33 Mb.
#142109
1   ...   27   28   29   30   31   32   33   34   ...   56
dokumen.tips aoemaalumotlar-tuzilmasi-va-ekvivalentlik-implikatsiya-chiqarib-tashlash-va

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; 


69 
};
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 
1.
Agar tugunning otasi yo‟q bo‟lsa, bu tugun ildiz hisoblanadi. Buni 
aniqlash uchun dastur kodini keltiramiz. Dasturda p izlanayotgan tugun. 


70 
if(p==tree) cout<<”bu tugun ildiz ekan”; 
else cout<<”bu tugun ildiz emas”; 
2.
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”; 
3.
Biz izlayotgan tugun terminal tugunligini tekshirishni ko‟rib chiqamiz. 
Agar tugunning har ikkala shoxi NULL ga teng bo‟lsa, bu 

Yüklə 1,33 Mb.

Dostları ilə paylaş:
1   ...   27   28   29   30   31   32   33   34   ...   56




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin