O’zbekiston Respublikasi Oliy va O’rta maxsus ta’lim vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universititeti Farg’ona filliali

4. Daraxtni aylanib o’tish (daraxt elementlarini o’qish). 
Daraxtlar bilan ishlashdagi asosiy amallardan biri daraxtni aylanib o’tish amali 
hisoblanadi. Bu yerda daraxtning har bir tugunini bir marta o’qish orqali barcha 
tugunlarni o’qib chiqish ko’zda tutilgan. Ya’ni, daraxtni aylanib o’tish natijasida 
barcha tugunlardagi element qiymatlari ma’lum bir tartibda chop etilishi kerak. 
Daraxtni aylanib o’tishning uchta varianti mavjud, masaln bizga quyidagi 
rasmda tasvirlangan daraxt berilgan bo’lsin: 
5-rasm. 

---

1) ICHO’ (ildiz - chap – o’ng) – birinchi ildiz o’qiladi (uning qiymati chop 
etiladi), keyin chap qismdaraxt (tugun) va undan keyin o’ng qismdaraxt (tugun) – {1, 
2, 4, 5, 3} 
2) CHIO’ (chap – ildiz – o’ng) – birinchi chap qismdaraxt, keyin ildiz, undan 
keyin o’ng qismdaraxt – {4, 2, 5, 1, 3} 
3) CHO’I (chap – o’ng – ildiz) – birinchi chap qismdaraxt, keyin o’ng 
qismdaraxt, undan keyin ildiz – {4, 5, 2, 3, 1} 
Misol uchun quyida daraxtni CHIO’ tartibida aylanib o’tishning rekursiv 
protsedurasi berilgan: 
void PrintChIO(PNode Tree) { 
if (! Tree) return; // agar daraxt bo’sh bo’lsa 
PrintLKP(Tree->left); // chap qismdaraxtni o’qish 
printf(”%d ”, Tree->key); // ildiz qiymatini chiqarish 
PrintLKP(Tree->right); // o’ng qismdaraxtni o’qish 
} 
Daraxtni aylanib o’tishning boshqa variantlari ham xuddi shunday shaklda 
tuziladi.
5. Daraxt yordamida qidiruv. 
Daraxt tuzilmasida elementlarni qidiruvni tashkil etishning eng qulay 
hisoblanadi. Buning uchun daraxtni maxsus ko’rinishda qurib olish talab etiladi. 
Faraz qilaylik, bizga qidiruvni tashkil etish uchun kalit-qiymatli massiv 
elementlari berilgan bo’lsin. Elementlar uchun kalit qiymati quyidagicha: 
59, 100, 75, 30, 16, 45, 250 
Berilgan qiymatlar ichida biz qidiorayotgan x kalitga mos keluvchi qiymatni 
aniqlash uchun, massivni to’liq ko’rib chiqishimiz kerak bo’ladi va ko’plab 
taqqoslashlar amalga oshiriladi. 
Agar massiv elementlar yuqoridagi ko’rinishda (tartiblanmagan – 
saralanmagan) bo’lsa, u holda bizga zarur bo’lgan element topilgunga qadar n marta 
taqqoslash amalini bajarishimizga to’g’ri keladi. Bu hol zarur ma’lumotni 
qidirishning eng yomon holati hisoblanadi. 
Qidiruvni soddalashtirish (yoki tezkorlikni ta’minlash) maqsadida berilgan 
massiv elementlaridan daraxtni quyidagi rasmda tasvirlangandek qurib olamiz. 

---

Bundjay daraxt – qidiruv daraxti deb ataladi, uni qurish uchun quyidagi qidiruv 
daraxtini qurishning asosiy xossadan foydalanamiz: 
x tugunning chap qism daraxtidagi barcha tugunlar kalit - qiymati x ning qiymatidan 
kichik, o’ng qismdaraxtidagi barcha tugunlarning kalit qiymati x ning qiymatidan 
katta yoki teng. 
6-rasm. 
Rasmda tasvirlangan daraxtda ixtiyoriy kalitga ega bo’lgan elementni qidirish 
uchun ko’pi bilan 3 ta taqqoslash amali bajariladi (elementlarning massiv 
ko’rinishida esa 7 ta taqqoslash bajarilar edi). Elementlar soni ko’payishi bilan 
qidiruv samaradorligi ham oshadi. 
Qidiruv daraxtini qurish: 
1. Daraxt ildizi kalit-qiymati bilan massivning navbatdagi elementi qiymatini 
taqqoslash. 
2. Agar yangi element qiymati kichik bo’lsa, uni chap qismdaraxtga, aks holda, 
ya’ni katta yoki teng bo’lganda o’ng qismdaraxtga qo’yish. 
3. Agar joriy daraxt bo’sh bo’lsa, yangi tugun hosil qilish va uni daraxtga 
qo’shish. 
Ushbu algoritmning dasturdagi tadbiqi quyidagicha bo’ladi: 
void AddToTree (PNode &Tree, //ildizga ko’rsatkich 
int data) { // kalitni qo’shish 
if (! Tree ) { 
Tree = new Node; // yangi tugun hosil qilish 
Tree->key = data; 

---

Tree->left = NULL; 
Tree->right = NULL; 
return; 
} 
if (data < Tree->key) // kerakli qismdaraxtni qo’shish 
AddToTree (Tree->left, data); 
else AddToTree (Tree->right, data); 
} 
Daraxt ildiziga ko’rsatkichni ssilka yordamida berish juda muhim, chunki u 
yangi tugun hosil qilishda o’zgarib turadi. Shuni alohida ta’kidlash kerakki, ushbu 
algoritm ishlashi natijasida hammavaqt ham minimal balandlikdagi daraxt hosil 
bo’lmaydi. Bu elementlarni tanlab olish tartibiga bog’liq bo’ladi. Qidiruvni 
optimallashtirish uchun odatda muovzonatlashgan yoki AVL- daraxt
[1]
 deb ataluvchi 
tuzilmadan foydalanish tavsiya etiladi. Bunday daraxtlarda ixtiyoriy tugunning o’ng 
va chap qismdaraxtlari balandligining farqi 1 dan oshmaydi. Ba’zida bunday daraxtga 
yangi element qo’shish uchun daraxtni qayta qurishga to’g’ri keladi. 
Daraxt bo’yicha qidiruv. Qidiruv daraxtini qurish natijasida elementlar 
saralangan ikki qismga ajraladi. Daraxt bo’yicha qidirishda birinchi o’rinda ildiz 
qiymati taqqoslanadi, agar qiymat qidirilayotgan qiymatga teng bo’lsa, u holda dastur 
o’z ishini yakunlaydi. Agarda ildiz qiymatidan kichik bo’lsa, chap qismdaraxt 
bo’ylab qidiruv davom ettiriladi, katta bo’lsa, o’ng qismdaraxt bo’ylab qidiriladi. 
Quyidagi ko’rsatilgan qidiruv funktsiyasi agar qidiruv samarali yakunlangan bo’lsa, 
zarur 
tugunning 
adres 
qiymatini 
qaytaradi, 
aks 
holda 
element 
topilmasa, NULL qiymatini qaytaradi. 
PNode Search (PNode Tree, int what) { 
if (!Tree) return NULL; //kalit topilmadi 
if (what == Tree->key) return Tree; //kalit topildi 
if (what < Tree->key) // qismdaraxtlardan qidirish 
return Search (Tree->left, what); 
else return Search (Tree->right, what); 
} 

---

Qidiruv daraxti yordamida saralash. Agar qidiruv daraxti qurilgan bo’lsa, u 
holda saralangan ma’lumotlarni chiqarish juda oson, bunda daraxtni CHIO’ (chap 
qismdaraxt – ildiz – o’ng qismdaraxt) usulida aylanib o’tsak ma’lumotlar o’sish 
tartibida, agarda O’ICH (o’ng qismdaraxt – ildiz – chap qismdaraxt) usulida aylanib 
o’tsak kamayish tartibida saralangan ma’lumotlarga ega bo’lamiz. 
Bir xil qiymatli elementlarni qidirish. Keltirilgan algoritmni sonli massivda bir 
xil qiymatli elementlarni tezkor qidirish bo’yicha takomillashtish mumkin. Albatta, 
bunday holda massivning barcha elementlarini olib ularni o’zaro taqqoslab chiqish 
mumkin. Bunday holda taqqoslashlar soni ortib ketadi. Ikkilik daraxt yordamida 
bunday qidiruvning tezkorligini oshirish mumkin. Buning uchun tuzilma tugunlariga 
yana bitta count maydonini qo’shish kerak bo’ladi. Bu maydon topilgan elementning 
nusxalari (dublikatlari) sonini saqlaydi. 
struct Node { 
int key; 
int count; // dublikatlar sanagichi 
Node *left, *right; 
}; 
Tugunni hosil qilishda sanagichga element topilsa bir soni yoziladi. Bir 
qiymatli elementlarni (dublikatlarni) qidirish quyidagi algoritm bo’yicha amalga 
oshiriladi: 
1. Massivning navbatdagi elementi kalitini ildiz kaliti bilan taqqoslash. 
2. Agar yangi element kaliti ildiz kalitiga teng bo’lsa, ildiz sanagichini bir 
birlikka oshirish va to’xtatish. 
3. Agar yangi element kaliti ildiz kalitidan kichik bo’lsa, u holda uni chap 
qism daxatga qo’shish, agar katta yoki teng bo’lsa, o’ng qismdaraxtga qo’shish. 
4. Agar joriy daraxt bo’sh bo’lsa, yangi (schetchigi 1 teng bo’lgan) tugunni 
hosil qilish va daraxtga qo’shish.