Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

5-qism. Daraxtlar 
Ushbu  mavzuning  boshidan  bog’langan  ro’yxat  tushunchasidan  daraxt 
tushunchasini  o’rganishni  boshlaymiz.  Bu  tasodif  emas,  chunki  bog’langan 
ro’yxatlar  ham  daraxt  tuzilmalari  ham  rekursiya  asosida  quriladi.  Aslida, 
bog’langan  ro’yxatlar  daraxt  tuzilmasining  bir  ko’rinishi  hisoblanadi.  Ushbu 
mavzuda daraxtlarni qurishning asosiy printsiplari va daraxt tugunlarini aylanib 
o’tish (tugunlarni ma’lum tartibda o’qish) ning turli xil usullarini qarab chiqamiz.  
5.1. Asosiy tushunchalar 
Daraxt  tushunchasi  19-asrning  o’rtalariga  kelib  matematikada  paydo 
bo’ldi,  keyin  daraxt  tushunchasi  turli  xil  sohalarda,  masalan,  elektr  tarmoqlari 
nazariyasi yoki kimyoviy izometriya sohalarida keng qo’llanila boshladi. Daraxt 
ko’rinishida  tuzilmalardan  axborot  texnologiyalarida  20-asrning  60-yillarida 
algebra  formulalarini  tadbiq  qilishda  qo’llaniladi  boshladi,  taxminan  shu 
davrlarda daraxtni aylanib o’tishning an’anaviy algoritmlari paydo bo’lgan.  
Umumiy  ma’noda  daraxt  –  bu  ob’ektlar  majmuasini  saqlovchi  ierarxik 
tuzilma.  Komp’yuter  texnologiyalarida  daraxt  tuzilmalari  keng  qo’llaniladi, 
masalan fayl tizimlarini tashkil etishda fayl va katologlarning ierarxik tuzilmasini 
hosil  qilishda  keng  qo’llanilgan.  Daraxt  (ingl.  tree)  —  aniq  talablarni 
qanoatlantiruvchi bo’sh bo’lmagan qirra (tugun)lar va yoylar majmuasi. Cho’qqi 
(ingl. vertex) — ro’yxatdagiga o’xshash tugun (ingl. node) deb ham ataladigan 
ob’ekt,  bu  ob’ekt  o’z  navbatida  nomga  ega.  Daraxtning  asosiy  xususiyati  — 
ixtiyoriy ikkita tugunlari orasida ularni bog’lovchi faqat bitta yo’l (yoy) mavjud. 
Agar  qandaydir  tugunlar  juftligi  orasida  yoylar  soni  bittadan  ko’p  yoki  yoy 
mavjud  bo’lmasa,  bunday  tuzilma  graf  deb  ataladi.  Bog’lanmagan  daraxtlar 
to’plami o’rmon (ingl. forest) deb ataladi. 
Tugunlarni aniqlash uchun quyidagi atamalar qo’llaniladi: 
root – bu daraxt ildizida joylashgan tugun; 
siblings – bitta otaga ega bo’lgan tugunlar; 
ancestor yoki parent – ota tugun; 

---

77 
 
descendant – o’g’il tugun; 
size  –  o’g’il  tugunlar  soni  qo’shilgan  birga  teng  bo’lgan  son,  tugun 
o’lchami. 
Ushbu  mavzuda  ixtiyoriy  sondagi  o’g’il  tugunlarga  ega  bo’lgan  daraxt 
tuzilmalarini tahlil qilamiz. Tartiblangan (ingl. ordered) daraxt — bu har bir tugun 
uchun  o’g’il  tugunlar  ketma-ketligi  tartibi  aniqlangan  aniq  ildiz  tugunga  ega 
bo’lgan daraxt.  
Daraxtlar quyidagi sinflarga ajratiladi: 
- ildizsiz daraxt; 
- ildizli daraxt; 
- tartiblangan daraxt; 
- m-ar (o’lchamli) va binar daraxt. 
1-rasmda 
kitob 
mundarijasining 
daraxt 
ko’rinishi  tasvirlangan. 
Ko’rsatilgan misolda ildiz tugun uchta qismdaraxt – har biri o’z navbatida bob va 
paragraflardan tashkil topgan uchta qismdan iborat. 
 
1-rasm. Daraxt tuzilmasiga misol 
 
Yo’l (ingl. path) – bu ildiz tugundan uning o’g’il tugunlariga o’tish (borish) 
uchun tugunlar ketma-ketligi. Yo’l uzunligi tugunlar sonidan bittaga kam bo’ladi. 
Balandlik  (ingl.  height)  –  bu  ildizdan  eng  uzoqdagi  tugungacha  bo’lgan  yo’l. 
Masalan,  1-rasmdagi  1-QISM  qismdaraxtining  balandligi  1  ga  teng,  2-QISM 
qismdaraxtining balandligi 2 ga, 3-QISM qismdaraxtining balandligi 0 ga teng, 

---

78 
 
ya’ni bu qismdaraxt o’g’il tugunlarga ega emas. Odatda o’g’il tugunlar chapdan 
o’ngga  o’qiladi,  lekin  buni  turli  tartibda  amalga  oshirish  mumkin.  2-rasmda 
daraxtga misol keltirilgan va bu daraxtni uch xil usulda aylanib o’tish shakllari 
keltirilgan.  
 
2-rasm. Daraxt tuzilmasiga misol 
 
preorder – yuqoridan-pastga-chapdan-o’ngga: F, B, A, D, C, E, G, I, H; 
inorder – chapdan-yuqoriga-pastdan-o’ngga: A, B, C, D, E, F, G, H, I; 
postorder – o’g’illardan ota (ildiz)ga teskari harakat: A, C, E, D, B, H, I, G, 
F. 
Agar  daraxt  tuzilmasi  bilan  bog’langan  ro’yxat  to’zilmalarini 
solishtiradigan  bo’lsak,  daraxt  tuzilmasida  tugun  qo’shish  va  tugnni  o’chirish 
amallari ancha murakkab ekanligini ko’rishimiz mumkin. Masalan, binar daraxt 
tugunini  o’chirishda  uning  ikkita  o’g’il  tugunlaridan  qaysi  biri  o’chirilgan  ota 
tugun o’rnini bosa olishi muammosini hal qilish zarur bo’ladi.