O’zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo’mitasi
| info
|
|
right |
4.3-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; 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
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;sontinue;} next=tree;
while(1){ last=next;
if(p->info
}
if(p->info
}
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 (4.4-rasm).
4.4-rasm. Binar daraxt elementlarini belgilash
Shunday qilib binar daraxtini ham yaratib oldik. Endigi masala uni ekranda tasvirlash kerak, ya’ni u ko‟rikdan o‟tkaziladi yoki vizuallashtirsa ham bo‟ladi.
Daraxt “ko‟rigi” funksiyalari
4.5-rasmdagidek binar daraxt berilgan bo‟lsin:
4.5-rasm. 3 ta elemetdan iborat binar daraxt
Binar daraxtlari ko‟rigini uchta tamoyili mavjud. Ularni berilgan daraxt misolida ko‟rib chiqaylik:
Yuqoridan pastga ko‟rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq ko‟rikdan o‟tkaziladi): A, B, C ;
Chapdan o‟ngga: B, A, C ;
Quyidan yuqoriga (ildiz qism daraxtlardan keyin ko‟riladi): B, C, A .
Daraxt ko‟rigi ko‟pincha ikkinchi usul bilan, ya’ni tugunlarga kirish ularning kalit qiymatlarini o‟sish tartibida amalga oshiriladi.
Yüklə 0,92 Mb.
Dostları ilə paylaş:
