Mavzu: Daraxtsimon maʻlumotlar tuzilmalari. Taʻriflar va xususiyatlari. Reja

Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti
Bajardi: Muzaffarov Feruzjon
Takshirdi: Akbarova Marg’uba
Mavzu: Daraxtsimon maʻlumotlar tuzilmalari. Taʻriflar va xususiyatlari. Reja:
1.Mavzu bo’yicha ma’lumotlar
2.Amaliy ish
3.Ish natijasi
4.Xulosa

Uzellar (elementlar) va ularning munosabatlaridan iborat elementlar

to‟plamining ierarxik tuzilmasiga daraxtsimon ma‟lumotlar tuzilmasi
deyiladi.

Daraxt – bu shunday chiziqsiz bog‟langan ma‟lumotlar tuzilmasiki, u quyidagi belgilari

bilan tavsiflanadi:
- daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo‟q. Bu
element daraxt ildizi deyiladi;
- daraxtda ixtiyoriy element chekli sondagi ko‟rsatkichlar yordamida boshqa tugunlarga
murojaat qilishi mumkin;
- daraxtning har bir elementi faqatgina o‟zidan oldingi kelgan bitta element bilan
bog‟langan.
Binar daraxtlarni qurish
Binar daraxtda har bir tugun-elementdan ko‟pi bilan 2 ta shox chiqadi. Daraxtlarni
xotirada tasvirlashda uning ildizini ko‟rsatuvchi ko‟rsatkich berilishi kerak. Daraxtlarni
kompyuter xotirasida tasvirlanishiga ko‟ra har bir element (binar daraxt tuguni) to‟rtta
maydonga ega yozuv shaklida bo‟ladi, ya‟ni kalit maydon, informatsion maydon, ushbu
elementni o‟ngida va chapida joylashgan elementlarning xotiradagi adreslari saqlanadigan
maydonlar.
Daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o‟g‟il qiymati kichik kalitga,
o‟ng tomondagi o‟g‟il esa katta qiymatli kalitga ega bo‟ladi. Har safar daraxtga yangi
element kelib qo‟shilayotganda u avvalambor daraxt ildizi bilan solishtiriladi. Agar element
ildiz kalit qiymatidan kichik bo‟lsa, uning chap shoxiga, aks holda o‟ng shoxiga o‟tiladi.
Agar o‟tib ketilgan shoxda tugun mavjud bo‟lsa, ushbu tugun bilan ham solishtirish amalga
oshiriladi, aks holda, ya‟ni u shoxda tugun mavjud bo‟lmasa, bu element shu tugunga
joylashtiriladi.
Masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101. U holda binar
daraxt ko‟rinishi quyidagi 1-rasmdagidek bo‟ladi:

1-rasm. Binar daraxt ko‟rinishi

Natijada, o‟ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt hosil qildik.
Agar daraxtning o‟ng va chap qism daraxtlari bosqichlarining farqi birdan kichik bo‟lsa,
bunday daraxt ideal muvozanatlangan daraxt deyiladi. Yuqorida hosil qilgan binar
daraxtimiz ideal muvozanatlangan daraxtga misol bo‟ladi
Binar daraxt yaratish funksiyasi
Binar daraxtni hosil qilish uchun kompyuter xotirasida elementlar quyidagi 2-
rasmdagidek ko’rinishda bo‟lishi lozim:
2-rasm. Binar daraxt elementining tuzilishi
p – yangi element ko‟rsatkichi
next, last – ishchi ko‟rsatkichlar, ya‟ni joriy elementdan keyingi va oldingi elementlar
ko‟rsatkichlari
r=rec – element haqidagi birorta ma‟lumot yoziladigan maydon
k=key – elementning unikal kalit maydoni
left=NULL – joriy elementning chap tomonida joylashgan element adresi
right=NULL – joriy elementning o‟ng tomonida joylashgan element adresi.
Dastlab yangi element hosil qilinayotganda bu ikkala maydonning qiymati 0 ga teng
bo‟ladi.
tree – daraxt ildizi ko‟rsatkichi
n – daraxtdagi elementlar soni
Boshida birinchi kalit qiymat va yozuv maydoni ma‟lumotlari kiritiladi, element hosil
qilinadi va u daraxt ildiziga joylashadi, ya‟ni tree ga o‟zlashtiriladi. Har bir hosil qilingan

yangi elementning left va right maydonlari qiymati 0 ga tenglashtiriladi. Chunki bu element

daraxtga terminal tugun sifatida joylashtiriladi, hali uning farzand tugunlari mavjud emas.
Qolgan elementlar ham shu kabi hosil
qilinib, kerakli joyga joylashtiriladi. Ya‟ni kalit qiymati ildiz kalit qiymatidan kichik
bo‟lgan elementlar chap shoxga, katta elementlar o‟ng tomonga joylashtiriladi. Bunda agar
yangi element birorta elementning u yoki bu tomoniga joylashishi kerak bo‟lsa, mos
ravishda left yoki right maydonlarga yangi element adresi yozib qo‟yiladi.
Binar daraxtni hosil qilishda har bir element yuqorida ko‟rsatilgan toifada bo‟lishi kerak.
Lekin biz o‟zlashtirish osonroq va tushunarli bo‟lishi uchun key va rec maydonlarni bitta
qilib info maydon deb ishlatamiz.
Ushbu toifada element hosil qilish uchun oldin bu toifani yaratib olishimiz kerak. Uni
turli usullar bilan amalga oshirish mumkin. Masalan, node nomli yangi toifa yaratamiz:
class node{ 
public: 
int info; 
node *left; 
node *right; }; 
Endi yuqoridagi belgilashlarda keltirilgan ko‟rsatkichlarni shu toifada yaratib olamiz.
node *tree=NULL; 
node *next=NULL; 
int n,key; cout<<"n=";
cin>>n; 
Nechta element (n) kiritilishini aniqlab oldik va endi har bir element qiymatini kiritib,
binar daraxt tuzishni boshlaymiz.
for(int i=0;i
node *last=new node; 
cin>>key; 
p->info=key; 
p->left=NULL; 
p->right=NULL; 
if(i==0){ tree=p; next=tree;sontinue;} 
next=tree; 
while(1){ last=next; 
if(p->infoinfo) next=next->left; else next=next->right; 
if(next==NULL) 
break; } if(p->infoinfo) last->left=p; else last->right=p;} 
Bu yerda p - kiritilgan kalitga mos hosil qilingan yangi element ko‟rsatkichi, next yangi
element joylashishi kerak bo‟lgan joyga olib boradigan shox adresi ko‟rsatkichi, ya‟ni u

har doim p dan bitta qadam oldinda yuradi, last esa ko‟rilayotgan element kimning avlodi

ekanligini bildiradi, ya‟ni u har doim p dan bir qadam orqada yuradi (4-rasm).
4-rasm. Binar daraxt elementlarini belgilash
Daraxt “ko‟rigi” funksiyalari
Binar daraxt quyidagicha berilgan bo‟lsin:
5-rasm. 3 ta elemetdan iborat binar daraxt
Binar daraxtlari ko‟rigini 3 tamoyili mavjud.
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.
Daraxt ko‟rigining rekursiv funksiyalari
1. i
nt 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

pretrave(tree->left); 
pretrave(tree->right); } return 0; }; 
2. int intrave(node *tree){if(tree!=NULL) {intrave(tree->left); 
cout
intrave(tree->right); } return 0; }; 
3. int postrave(node *tree){ 
if(tree!=NULL) { 
postrave(tree->left); 
postrave(tree->right); 
cout
Daraxtning har bir tuguni 6-rasmdagidek oraliq (2, 3, 5, 7 elementlar) yoki
terminal (daraxt “barg”i) (4, 9, 10, 11, 8, 6 elementlar) bo‟lishi mumkin.
6-rasm. Daraxtsimon tuzilma
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 
terminal tugun hisoblanadi. Dastur kodini
keltiramiz.
if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal tugun”; 
else cout<<”bu terminal tugun emas”; 
 
 
1.
Binar Daraxt ustida quyidagi amallar bajarilsin:
- Daraxtning ildizini hosil qilish;
- Daraxtga element qo’shish;
- Daraxtdan element o’chirish;
- Daraxtda element mavjudligini tekshirish;
2. Binar Daraxt tugunlari haqiqiy sonlar bo’lsin. Quyidagi ishlarni bajaruvchi prosedura
ѐki funksiyani ѐzing:
- daraxt barcha tugunlarini o’rta arifmetik qiymatini hisoblash;
- qiymati yuqoridagi prosedura(funksiya)da hosil bo’lgan songa teng elementni
daraxtga qo’shish.