Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI

UNIVERSITETI FARG’ONA FILIALI

“Ma’lumotlar tuzulmasi va algaritimi”


fanidan

Mustaqil ish

Bajardi: 730-21 guruh talabasi
Turg’unov I
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;

16. 
    >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<int h=height(tree); cout<<"balandligi="<}