4- Laboratoriya ishi. Rekursiv malumotlar tuzilmasi va rekursiv
algaritmlarni tadqiq qilish.
Ishdan maqsad: Rekursiv ma’lumot tuzilmasini toifalarini o‘rganish va ularni
tadqiq qilish.
Qo‘yilgan masala: C++ tilida butun, haqiqiy, belgili, mantiqiy toifadagi
ma’lumotlarni e’lon qilish, nostandart toifalarni yaratish va ularga doir
misollarning dasturini ishlab chiqish.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Daraxt ko’rigini rekursiv prosedurlari:
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;
};
Binar daraxt bo’yicha qidiruv prosedurasi
Mazkur proseduraning
vazifasi shundan iboratki, u berilgan kalit bo’yicha
daraxt tuguni qidiruvini amalga oshiradi. Qidiruv
operasiyasining davomiyligi
daraxt tuzilishiga bog’liq bo’ladi.
Haqiqatdan, agar
elementlar daraxtga kalit
qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa,
u holda daraxt bir
tomonga yo’nalgan ro’yxat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona
shohga ega), masalan:
Bu
holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yxatdagi
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 prosedurasini ko’rib chiqamiz. search o’zgaruvchisiga
topilgan
bo’g’in ko’rsatkichi o’zlashtiriladi:
int search(node *tree, int key){
node *next; next=tree;
while(next!=NULL) { if (next->info==key){cout<<"Binar daraxtda
"<
