“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

 
4.3. Algoritm 
Binar daraxt yaratish funksiyasi 
Binar daraxtni hosil qilish uchun kompyuter xotirasida elementlar quyidagi
4.2-rasmdagidek toifada bo‟lishi lozim. 
4.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 

---

66 
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 hozir biz o‟zlashtirish osonroq va tushunarli bo‟lishi uchun 
key va rec maydonlarni bitta qilib info maydon deb ishlatamiz. 
4.3-rasm. Binar daraxt elementining tuzilishi 
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