Ikkilik daraxtlar va ular ustida amallar

Информация о документе

Цена	15000UZS
Размер	984.0KB
Покупки	0
Дата загрузки	17 Апрель 2025
Расширение	docx
Раздел	Образовательные программы
Предмет	Информатика и ИТ

Продавец

Mengnorov Ergash

Дата регистрации 15 Апрель 2025

0 Продаж

Ikkilik daraxtlar va ular ustida amallar

Купить

Binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. Binar daraxt
balandligini aniqlash uchun uning har bir tuguni chap va o’ng qism daraxtlari
balandliklari solishtiriladi va maksimal qiymat balandlik deb olinadi.
Daraxt balandligini aniqlash dastur kodini keltiramiz:
int height(node *tree){
int h1,h2;
if (tree==NULL) return (-1);
else {
h1 = height(tree->left);
h2 = height(tree->right);
if (h1>h2) return (1 + h1);
else return (1 + h2);
}
}
Agar daraxtni tashkil etuvchi elementlardan ko`pi bilan 2 ta shox chiqsa,
ya’ni har bir tugun tuzilmaning ko`pi bilan 2 ta tuguni bilan bog`langan bo`lsa, u
holda bunday daraxt binar daraxt deyiladi. Binar daraxt — bu ma’lumotlar
tuzilmasining maxsus turi bo‘lib, har bir tugun ko‘pi bilan ikkita bolaga ega
bo‘ladi. Tugunlar odatda ikki qismga bo‘linadi:
1.Chap bola (left child)
2.O‘ng bola (right child)
Quyidagi 1-rasmda binar daraxtga misol keltirilgan.

1-rasm.Binar daraxt.
Binar daraxtda har bir tugun-elementdan ko’pi bilan 2 ta shox chiqadi.
Daraxtlarni xotirada tasvirlashda uning ildizini ko’rsatuvchi ko’rsatkich berilishi
kerak. Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra har bir element
to’rtta maydonga ega yozuv shaklida bo’ladi, ya’ni kalit maydon, informatsion
maydon, ushbu elementni o’ngida va chapida joylashgan elementlarning xotiradagi
adreslari saqlanadigan maydonlar.
Shuni esda tutish lozimki, daraxt hosil qilinayotganda, otaga nisbatan chap
tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli
kalitga ega bo’ladi. Har safar daraxtga yangi element kelib qo’shilayotganda u
avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan
kichik bo’lsa, uning chap shoxiga, aks holda o’ng shoxiga o’tiladi. Agar o’tib
ketilgan shoxda tugun mavjud bo’lsa, ushbu tugun bilan ham solishtirish amalga
oshiriladi, aks holda, ya’ni u shoxda tugun mavjud bo’lmasa, bu element shu
tugunga joylashtiriladi.
Masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101 . U
holda binar daraxt ko’rinishi quyidagi 2-rasmdagidek bo’ladi:

2-rasm.Binar daraxt qurish
Natijada, o’ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt
hosil qildik. Agar daraxtning o’ng va chap qism daraxtlari bosqichlarining farqi
birdan kichik bo’lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi.
Yuqorida hosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol
bo’ladi. Daraxtni muvozanatlash algoritmini sal keyinroq ko’rib chiqamiz. Undan
oldin binar daraxtni yaratish algoritmini o’rganamiz.
Binar daraxt yaratish funksiyasi
Binar daraxtni hosil qilish uchun kompyuter xotirasida elementlar quyidagi
3-rasmdagidek toifada bo’lishi lozim.
3-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
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-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; left rightinfo

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<n;i++){
node *p=new node;
node *last=new node;
cin>>key;
p->info=key;
p->left=NULL;
p->right=NULL;
if(i==0){ tree=p; next=tree;continue;}
next=tree;
while(1){ last=next;
if(p->info<next->info) next=next->left; else next=next->right;
if(next==NULL) break;
}

if(p->info<last->info) last->left=p; else last->right=p;
}
Bu yerda p hali aytganimizdek, kiritilgan kalitga mos hosil qilingan yangi
element ko’rsatkichi, next yangi element joylashishi kerak bo’lgan joyga olib
boradigan shox adresi ko’rsatkichi, ya’ni u har doim p dan bitta qadam oldinda
yuradi, last esa ko’rilayotgan element kimning avlodi ekanligini bildiradi, ya’ni u
har doim p dan bir qadam orqada yuradi ( 5 -rasm).
5-rasm.Binar daraxt elementlarini belgilash
Shunday qilib binar daraxtini ham yaratib oldik. Endigi masala uni ekranda
tasvirlash kerak, ya’ni u ko’ruvidan o’tkaziladi.Ko’ruv bu binar daraxti ustida
bajariladigan amallari sirasiga kiradi.
Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.
1) Agar maksimal darajasi m bo’lsa, u holda bunday daraxt m-tartibli daraxt
deyiladi;
2) Agar chiqish darajasi 0 yoki m bo’lsa, u holda to’liq m – tartibli daraxt deyiladi;
3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt bi nar daraxt
deyiladi;
4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binar daraxt deyiladi.
Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda
ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga

oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan
ko’rsatkichlar maydoniga ega bo’ladi.
Binar daraxti ustida bajariladigan asosiy amallar.
1. Daraxt ko’ruvi (elementlarni ma’lum bir ko’rinishda tartiblash yoki chop etish).
2.Daraxtga yangi tugun qo’yish.
3.Daraxt tugunini o’chirish.
4.Daraxt tugunini qidirish.
Daraxt ko’ruvi
6-ram. 3 ta elemetdan iborat binar daraxt .
Binar daraxtlari ko’ruvining uchta tamoyili mavjud. Ularni berilgan daraxt
misolida ko’rib chiqaylik:
1) Yuqoridan pastga ko’rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq
ko’rikdan o’tkaziladi): A, B, C ;
2) Chapdan o’ngga: B, A, C ;
3) Quyidan yuqoriga (ildiz qism daraxtlardan keyin ko’riladi): B, C, A .
Daraxtga yangi element qo‘shish funksiyasi
Daraxtga biron bir tugun qo’shishdan oldin daraxtga berilgan kalit bo’yicha
qidiruvni amalga oshirish lozim bo’ladi. Agar berilgan kalitga teng kalitli tugun
mavjud bo’lsa, u xolda dastur o’z ishini yakunlaydi, aks holda daraxtga tugun
qo’yish amalga oshiriladi.

Daraxtda yangi tugun faqatgina ko’rsatgichlarini kamida bittasi bo’sh bo’lgan
tugundan keyin qo’yiladi.
Daraxtda qo’shilayotgan element kalitiga teng kalitli element yo’q bo’lgan
holda elementni tuzilmaga qo’shish funksiyasini keltirib o’tamiz.
Node *q=NULL;
Node *p=tree;
while(p!=NULL){
q=p;
if(key==p->key){
search=p;
return 0;
}
If(key<p->key) p=p->left;
else p=p->right;
}
Berilgan kalitga teng tugun topilmadi, element qo’shish talab qilinadi. Ota
bo’lishi mumkin tugunga q ko’rsatkich beriladi, elementning o’zi esa yangi nomli
ko’rsatkichi bilan beriladi.
node *q=new node;
Qo’yilayotgan yangi element chap yoki o’ng o’g’il bo’lishini aniqlash lozim.
If(key<q->key) q->left=yangi;
else q->right=yangi;
search=yangi;
return 0;

Binar daraxtdan elementni o’chirish funksiyasi
Tugunni o’chirib tashlash natijasida daraxtning tartiblanganligi buzilmasligi
lozim.
Tugun daraxtda o’chirilayotganda 3 xil variant bo’lishi mumkin:
1) Topilgan tugun terminal (barg). Bu holatda tugun otasining qaysi tomonida
turgan bo’lsa, otasining o’sha tomonidagi shoxi o’chiriladi va tugunning xotirada
joylashgan sohasi tozalanadi.
2) Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga
joylashtiriladi.
3) O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism
daraxtlar zvenosini topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish
mumkin bo’lsin. Bunday zveno har doim mavjud bo’ladi:
- bu yoki chap qism daraxtning eng o’ng tomondagi elementi (ushbu zvenoga
erishish uchun keyingi uchiga chap shox orqali o’tib, navbatdagi uchlariga esa,
murojaat NULL bo’lmaguncha, faqatgina o’ng shoxlari orqali o’tish zarur);
- yoki o’ng qism daraxtning eng chap elementi (ushbu zvenoga erishish uchun
keyingi uchiga o’ng shox orqali o’tib, navbatdagi uchlariga esa, murojaat NULL
bo’lmaguncha, faqatgina chap shoxlari orqali o’tish zarur).
O’chirlayotgan element chap qism daraxtining eng o’ngidagi element
o’chirilayotgan element uchun merosxo’r bo’ladi ( 12 uchun – 11 bo’ladi).
Merosxo’r esa o’ng qism daraxtning eng chapidagi tuguni (12 uchun - 13).
Merosxo’rni topish algoritmini ishlab chiqaylik ( 7-rasmga qarang ).
p – ishchi ko’rsatkich;
q - p dan bir qadam orqadagi ko’rsatkich;
v – o’chirilayotgan tugun merosxo’rini ko’rsatadi;

t – v dan bir qadam orqada yuradi;
s - v dan bir qadam oldinda yuradi (chap o’g’ilni yoki bo’sh joyni ko’rsatib boradi).
7-rasm.Binar daraxtdan oraliq tugunni o’chirish tartibi.
Yuqoridagi daraxt bo’yicha qaraydigan bo’lsak, oxir oqibatda, v ko’rsatkich 13
tugunni, s esa bo’sh joyni ko’rsatishi lozim.
1) Elementni qidirish funksiyasi orqali o’chirilayotgan elementni topamiz. p
ko’rsatkich o’chirilayotgan elementni ko’rsatadi.
2) O’chiriladigan elementning o’rniga qo’yiluvchi tugunga v ko’rsatkich qo’yamiz.
node *del(node *tree,int key){
node *p=new node;
node *next=tree;
node *q=NULL;
while(next!=NULL)
{ if (next->info==key){cout<<"Binar daraxtda "<<key<<" Mavjud"<<endl;
p=next;break; }
if (next->info>key){ q=next; next=next->left; }
else {q=next;next=next->right;}
}

$if(next==NULL) cout<<"tuzilmada izlangan element yo’q!!!"<<endl; node *v=NULL,*t=NULL,*s=NULL; if(p->left==NULL)v=p->right; else if(p->right==NULL) v=p->left; if((p->left!=NULL)&&(p->right!=NULL)){t=p; v=p->right; s=v->left;} while(s!=NULL){ t=v; v=s; s=v->left; } if((t!=NULL)&&(t!=p)){ t->left=v->right; v->right=p->right; v->left=p->left; } if(t==p) v->left=p->left; if(q==NULL){ cout<<v->info<<" ildiz\n"; tree=v; delete(p); return tree; }$

if(p==q->left)
q->left=v;
else q->right=v;
delete(p); // o’chirilgan element joylashgan xotira yacheykasini tozalash
return tree;
}
Binar daraxtda qidiruv
Mazkur prodseduraning vazifasi shundan iboratki, u berigan kalit bo’yicha
daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi
daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit
qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir
tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi 1 bo’ladi, ya’ni yagona
shohga ega).
8-rasm.Binar daraxtda qidiruv.
Bu holatda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi
bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.
Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi.
Yuqorida keltirilgan bir nechta algoritmlarga misol ko’rib chiqamiz.
MISOL1 .Kiritilgan n ta sonlardan binar daraxti qursin va daraxt balandligi
topilsin.

KOD QISMI:
#include <iostream>
using namespace std;
class node {
public:
int info;
node *left;
node *right;
node(int val) {
info = val;
left = right = NULL;
}
};
int height(node *tree) {
if (tree == NULL) return -1;
int h1 = height(tree->left);
int h2 = height(tree->right);
return max(h1, h2) + 1;
}
node* insert(node* tree, int value) {
if (tree == NULL) {
return new node(value);
}

if (value < tree->info) {
tree->left = insert(tree->left, value);
} else {
tree->right = insert(tree->right, value);
}
return tree;
}
void inorder(node* tree) {
if (tree == NULL) return;
inorder(tree->left);
cout << tree->info << " ";
inorder(tree->right);
}
void vizual(node* tree, int level) {
if (tree == NULL) return;
vizual(tree->right, level + 1);
for (int i = 0; i < level; i++) cout << " ";
cout << tree->info << endl;
vizual(tree->left, level + 1);
}
int main() {
int n, s;
node *tree = NULL;

$cout << "n = "; cin >> n; cout << "Binar daraxt uchun elementlarni kiriting:\n"; for (int i = 0; i < n; i++) { cin >> s; tree = insert(tree, s); } cout << "\nDaraxtning grafikali ko‘rinishi:\n"; vizual(tree, 0); int h = height(tree); cout << "\nDaraxtning balandligi: " << h << endl; return 0; } NATIJA:$

MISOL2. Kiritilgan sonlardan binar daraxt yasab beruvchi va tugunni qidirb
topuvchi dastur yarating.Dastur ishlaganda qidirgan elementingizni mavjud yoki
mavjud emasligini topsin.
KOD QISMI:
#include <iostream>
using namespace std;
class node {
public:
int info;
node *left;
node *right;
node(int val) {
info = val;

left = right = NULL;
}
};
node* insert(node* tree, int value) {
if (tree == NULL) {
return new node(value);
}
if (value < tree->info) {
tree->left = insert(tree->left, value);
} else {
tree->right = insert(tree->right, value);
}
return tree;
}
node* search(node* tree, int value) {
if (tree == NULL || tree->info == value) {
return tree;
}
if (value < tree->info) {
return search(tree->left, value);
} else {
return search(tree->right, value);
}

$} void vizual(node* tree, int level) { if (tree == NULL) return; vizual(tree->right, level + 1); for (int i = 0; i < level; i++) cout << " "; cout << tree->info << endl; vizual(tree->left, level + 1); } int main() { int n, s, searchValue; node *tree = NULL; cout << "Daraxtga nechta element qo'shmoqchisiz? "; cin >> n; cout << "Binar daraxt uchun elementlarni kiriting:\n"; for (int i = 0; i < n; i++) { cin >> s; tree = insert(tree, s); } cout << "\nDaraxtning grafikali ko‘rinishi:\n"; vizual(tree, 0); cout << "\nQidirilayotgan qiymatni kiriting: "; cin >> searchValue; node* result = search(tree, searchValue);$ $if (result != NULL) { cout << "Qiymat " << searchValue << " daraxtda mavjud.\n"; } else { cout << "Qiymat " << searchValue << " daraxtda mavjud emas.\n"; } return 0; } NATIJASI:$

FOYDALANILGAN ADABIYOTLAR
1. Aminov, K. A. (2012). Dasturlash va ma'lumotlar tuzilmalari.
2. Ismoilov, B. (2013). Algoritmlar va ma'lumotlar tuzilmalari.
3. Raxmonov, I. (2010). Algoritmlar va ma'lumotlar tuzilmalari bo‘yicha
dasturlash.
4. Yusupov, M. (2015). Dasturlash va algoritmlar.
5. Azimov, A. (2008). Kompyuter ilmiga kirish.

Ikkilik daraxtlar va ular ustida amallar

Купить

Информация о документе

Продавец

Ikkilik daraxtlar va ular ustida amallar

Похожие документы