5-Laboratoriya ishi. Daraxtsimon ma’lumotlar tuzilmasini tadqiq qilish




Download 0.83 Mb.
bet3/9
Sana13.05.2022
Hajmi0.83 Mb.
#21019
1   2   3   4   5   6   7   8   9
Bog'liq
5-Laboratoriya ishi. Daraxtsimon ma’lumotlar tuzilmasini tadqiq

5.4. Daraxt “ko’rigi” funksiyalari


5.5-rasmdagidek binar daraxt berilgan bo’lsin:



5.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.

5.5. Daraxt koriginingrekursivfunksiyalari


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

  1. int intrave(node *tree){

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

  1. int postrave(node *tree){

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



5.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.



if(p==tree) cout<<”bu tugun ildiz ekan”;
else cout<<”bu tugun ildiz emas”;

  1. 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”;

  1. Biz izlayotgan tugun terminal tugunligini tekshirishni ko’rib chiqamiz. Agar tugunning har ikkala shoxi NULL ga teng bo’lsa, bu terminal tugunhisoblanadi. Dastur kodini keltiramiz.

if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal tugun”;
else cout<<”bu terminal tugun emas”;



Download 0.83 Mb.
1   2   3   4   5   6   7   8   9




Download 0.83 Mb.

Bosh sahifa
Aloqalar

    Bosh sahifa



5-Laboratoriya ishi. Daraxtsimon ma’lumotlar tuzilmasini tadqiq qilish

Download 0.83 Mb.