6-ma’ruza. Binar daraxtlar

MA’LUMOTLAR TUZILMASI

6-MA’RUZA. Binar daraxtlar

REJA

1. 
   Binar daraxtlar.
   
2. 
   Ko’p o’lchamli daraxtni binar ko’rinishga keltirish.
   
3. 
   Daraxtlar ustidagi bajariladigan amallar.
   
4. 
   MERGE va SPLIT amallari
   

Kalitli so’zlar: rekursiya,rekursiv algoritm, rekursiv tuzilma, daraxt, ko’p o’lchamli daraxt, binar daraxt, ildiz, ota-o’g’il, terminal (barg), daraxt balandligi, chiqish darajasi, muvozanatlangan daraxt, kalit, daraxt qurish, tugun qo’shish, o’chirish, qidirish, daraxt ko’ruvi, daraxtlarni tasvirlash.




1. Binar daraxtlar

Binar daraxtlar eng ko’p foydalaniladigan daraxtlar turi xisoblanadi.

Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra xar bir element to’rtta maydonga ega yozuv xisoblanadi. Mazkur maydonlar qiymati mos ravishda yozuv kaliti bo’lib, boshqa elementlarga murojaatni ifodalaydi, ya’ni chapga-pastga, o’nga-pastga va yozuv matniga.
Shuni esda tutish lozimki, daraxt xosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli kalitga ega bo’ladi. Masalan, quyidagi elementlardan binar daraxt quramiz: 50, 46, 61, 48, 29, 55, 79. U quyidagi ko’rinishga ega bo’ladi:

Natijada, o’ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt xosil qildik. Agar daraxtning o’ng va chap qism daraxtlari bosqichlari farqi birdan kichik bo’lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. Yuqorida xosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol bo’ladi.
Binar daraxtni xosil qilish uchun kompyuter xotirasida elementlar quyidagi turda bo’lishi lozim:
C++ tilida binar daraxtlarni quyidagicha e’lon qilish mumkin:


struct Node{
int info;
Node *left, *right;
};