Kompyuter injiniring

 
MUHAMMAD AL-XORAZMIY NOMIDAGI 
TOSHKENT AXBOROT TEXNOLOGIYALARI 
UNIVERSITETI FARG’ONA FILIALI 
“KOMPYUTER INJINIRING” 
FAKULTETI 
 
“Ma’lumotlar tuzulmasi va algaritimi” 
fanidan 
 
 
Amaliy ish 
Bajardi: 
691-21 guruh talabasi 
Ma’rufjonov Maqsudjon 
Qabul qildi: 

11-MA’RUZA: DARAXTSIMON MA’LUMOTLAR TUZILMALARI. 
BINAR VA KO’PTARMOQLI DARAXTLAR. 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; inode *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(); 
}