Binar daraxtlar ustuda amallar

---

MA’RUZA №11 
TA’RIFLAR VA XUSUSIYATLAR. BINAR DARAXTLAR. BINAR DARAXTNI QURISH.  
BINAR DARAXTLAR USTUDA AMALLAR. 
1. Asosiy tushunchalar  
Daraxt — bu tugunlar (cho’qqilar) va ularni birlashtiruvchi yo’naltirilgan yoy
(shox)lar majmuasi bo’lib, har bir tugunga (ildizdan tashqari) bitta shox (kirish yoyi)
yo’naltirilgan bo’ladi.
Ildiz — bu daraxtning boshlang’ich tuguni bo’lib, unga kirish yoy (shox)lar
mavjud emas.
Daraxt tuzilmasiga misol sifatida biror bir shaxsning 
oila shajarasini olish 
 
mumkin. Bunda daraxt ildiziga ushbu shaxs joylashtirilsa, uning farzandlari uning
davomchisi (avlodi) sifatida keyingi tugunlarga joylashadi. Masalan, buyuk
sarkarda, davlat arbobi Amir Temur shajarasini olish mumkin.
Quyidagi rasmda bir nechta daraxt tuzilmasiga misollar keltirilgan:
Ichki (oraliq)
tugun – daraxt ildizidan keyingi o’z avlodiga ega bo’lgan
tugunlar. Masalan, 1a)-rasmda 2, 4, 6 tugunlari, 1b)-rasmda 3 va 5 tugunlar ichki
yoki oraliq tugun hisoblanadi.
Balandlik – daraxt barglarining maksimal bosqichi. Masalan, 1a) va b)
rasmlardagi daraxtlar balandligi 3 ga teng. 
2. Daraxtning rekursiv aniqlanishi  
Daraxt – bu tayanch rekursiv (o’z o’zi orqali aniqlangan) tuzilma hisoblanadi.
Daraxtning aniqlanishi ikki qismga bo’linadi, birinchisi – rekursiyaning tugallanish
shartining aniqlanishi, ikkinchisi esa rekursiyaning bajarilish mexanizmi.
1) bo’sh tuzilma 
daraxt hisoblanadi
;
2) daraxt – bu ildiz va unga bog’langan bir nechta daraxtcha (qismdaraxt)lardir.
Yuqoridagilardan kelib chiqqan holda daraxt tuzilmasini Bekus – Naur shaklida
quyidagicha ifodalash mumkin:
::= ( ) |
::=
::=
Daraxtni saqlash uchun zarur bo’lgan xotira o’lchami 
oldindan aniq 
 
bo’lmaydi, chunki, undan nechta tugun chiqishi ma’lum bo’lmaydi. 
Ikkilik daraxtlar
dasturlashda yoki ma’lum bir jarayonlarning bajarilishida ikkita imkoniyatdan faqat
bittasini qabul qilish zarur bo’lganda qo’llaniladi. 
Bundan keyin faqat ikkilik 
 
daraxtlar bilan ishlashga doir masalalarni ko’rib chiqamiz.
Qat’iy ikkilik daraxt deb, har bir ichki tugunlarida bo’sh bo’lmagan
qismdaraxtlari bo’lgan daraxtga aytiladi. 
Bu shuni anglatadiki
, qat’iy ikkilik
daraxtda barcha ichki tugunlarida albatta o’ng va chap qismdaraxt (tugun)lar bo’lishi
shart. Quyidagi rasmda a) va b) lar qat’iy ikkilik daraxt, c) va d) lar esa qat’iy emas.
int main()
{ int n,key,s; node *tree=0,*next=0;

---

cout<<"n="; cin>>n; int arr[n];
for(int i=0; i 
node *p=new node;
node *last=new node;
cin>>s;
p->info=s;
p->left=0;
p->right=0;
if(i==0){tree=p; next=tree; continue; }
next=tree;
while(1)
{ last=next;
if(p->infoinfo)next=next->left;
else next=next->right;
if(next==0)break; }
if(p->infoinfo)last->left=p;
else last->right=p;}
cout< 
cout<<"\nya'ni\n";
vizual(tree,0);
int h=height(tree);
cout<<"balandligi="<getch();
}