|
#include
#include
#include
#include
using namespace std;
struct tree
{
int data;
struct tree *lchild, *mchild, *rchild;
};
//daraxtni qadamma-qadam aylanib o’tish uchun
funktsiya
void iterativeInorder(tree* root)
{
87
stack nodeStack;
tree *_root, *curr = root;
_root = root;
for (;;)
{
if (curr != NULL)
{
nodeStack.push(curr);
curr = curr->lchild;
continue;
}
if (nodeStack.size() == 0)
{
if(_root != NULL)
{
curr = _root->rchild;
_root = NULL;
continue;
}
else return;
}
curr = nodeStack.top();
nodeStack.pop();
cout << curr->data << " ";
if(curr->mchild != NULL)
curr = curr->mchild;
else
curr = curr->rchild;
}
88
}
void iterativePreorder(tree* root)
{
stack nodeStack;
tree *_root, *curr = root;
_root = root;
for (;;)
{
while (curr != NULL)
{
cout << curr->data << " ";
nodeStack.push(curr);
curr = curr->lchild;
}
if (nodeStack.size() > 0)
{
curr = nodeStack.top();
nodeStack.pop();
if(curr->mchild != NULL)
curr = curr->mchild;
else
curr = curr->rchild;
}
else
{
if(_root != NULL)
{
curr = _root->rchild;
_root = NULL;
89
continue;
}
else return;
}
}
}
void iterativePostorder(tree* root)
{
tree *curr = root;
stack s1,s2;
s1.push(curr);
tree *tmp=NULL;
while (s1.size() > 0)
{
tmp = s1.top();
s1.pop();
s2.push(tmp);
if (tmp->lchild)
s1.push(tmp->lchild);
if (tmp->mchild)
s1.push(tmp->mchild);
if (tmp->rchild)
s1.push(tmp->rchild);
}
while(s2.size() > 0)
{
tmp = s2.top();
s2.pop();
cout << tmp->data << " ";
90
}
}
//daraxtga tugun qo’shish uchun funktsiya
struct tree * my_insert(struct tree *p,int n, int
dir)
{
struct tree *temp;
temp = (struct tree *)malloc(sizeof(struct
tree));
temp->data = n;
temp->lchild = temp->rchild=NULL;
if(p==NULL)
{
return temp;
}
else
{
if(dir ==0) // chapga
{
p->lchild = temp;
return temp;
}
else if(dir ==1) //o’rtaga
{
p->mchild = temp;
return temp;
}
else // o’ngga
{
91
p->rchild = temp;
return temp;
}
}
}
int main()
{
int x,y,i;
struct tree *root;
struct tree *node_2, *node_3, *node_5, *node_8;
struct tree *node_9,*node_6,*node_10,*node_4,*node_7;
root = NULL;
root = my_insert(root,1,0);
node_2 = my_insert(root,2,0);
node_3 = my_insert(root,3,1);
node_4 = my_insert(root,4,2);
node_5 = my_insert(node_3,5,0);
node_8 = my_insert(node_5,8,0);
node_9 = my_insert(node_5,9,2);
node_6 = my_insert(node_3,6,2);
node_10 = my_insert(node_6,10,1);
node_7 = my_insert(node_4,7,1);
iterativeInorder(root);
printf("\n");
iterativePreorder(root);
printf("\n");
iterativePostorder(root);
return 0;
}
92
5.4. Daraxtni taqdim etish shakllari
Daraxtni taqdim etish shakllaridan biri bu oddiy massiv orqali taqdim etish
usuli hisoblanadi. Tugunlari 1 dan n gacha raqamlangan T – daraxt berilan bo’lsin.
T daraxtni taqdim etish uchun har bir A[i] elementi tugunga yoki uning ota
tuguniga ko’rsatkichni saqlaydigan oddiy chiziqli A massivdan foydalanamiz.
Agar daraxtning i va j tugunlaridan j tugun i tugun uchun ota tugun bo’lsa, u holda
A[i] = j
Ildiz tugunni identifikatsiya qilish uchun uning ota tuguniga ko’rsatkichni
NULL ga aylantirish kerak:
A[i] = 0
Har bir tugun faqat bitta otaga ega bo’ilish mumkin. Bir vaqtning o’zida A
massivga tugun belgilarini saqlovchi L massivni birlashtiramiz. 3-rasmda har bir
tugun uchun ota tugunlar massiv ko’rinishida berilgan. Ammo, daraxtni bunday
ko’rinishda taqdim etishda o’g’il tugunlar qanday tartibda berilishi mavhum
bo’lib qoladi.
3-rasm. Daraxtni massiv ko’rinishida taqdim etish
Daraxtni taqdim etishning yana bir mumkin bo’lgan varianti – bu
daraxtning barcha tugunlaridan tashkil topgan bog’langan ro’yxatlardan
foydalanish usuli hisoblanadi. Buning uchun 4-rasmda ko’rsatilganidek, o’g’il
tugunlar ota tugunlar bilan bir joyda saqlanadi.
93
4-rasm. Daraxtni ro’yxat ko’rinishida taqdim etish
Bu rasmda 1 dan 10 gacha raqamlangan tugunlarning umumiy massivi
berilgan. Bu ro’yxatdagir ba’zi alohida tugunlarning ro’yxatda nuqtalar bilan
belgilangan o’g’il tugunlari mavjud. Lekin bu massiv o’zgarmas o’zlchamga
egaligi uchun daraxtga yangi tugun qo’shish mumkin emas.
5.5. Daraxt ko’rinishlari
Daraxtni ifodalash (ingl. expression tree) – bu arifmetik yoki mantiqiy
ifodalarni tasvirlash uchun mo’ljallangan binar daraxt ko’rinishlari hisoblanadi.
Buning uchun 5-rasmda ko’rsatilganidek operandlar daraxt barglariga
joylashtiriladi.
5-rasm. Ifodalarni tadbiqi qilish daraxtiga misollar
94
Daraxtning triply linked deb ataluvchi, chap va o’ng tugunlariga
ko’rsatkichlardan tashqari tugunlarida 6-rasmda ko’rsatilganidek, ota tugunga
ko’rsatkichlar saqlanadi.
6-rasm. triply linked daraxti
7-rasmda daraxtning yana bir qiziqarli ikkita varianti – xalqasimon daraxt
va ildizga ega bo’lmagan daraxt shakllari berilgan.
7-rasm. Daraxtning noan’anaviy ko’rinishlari
95
Xulosa
Axborot texnologiyalari sohasidagi ilmiy yo’nalishlarda daraxtlar
nazariyasi eng ko’p qo’llaniladi. Ilmiy sohadagi turli xil ko’plab masalalarni
yechishda daraxt tuzilmalari tadbiq qilinadi. Komp’yuter texnologiyalarida
saqlash algoritmlarini yaratish, axborotlarni qidirish va qayta ishlash uchun eng
muhim tuzilmalardan biri bu daraxt tuzilmasi hisoblanadi. Ixtiyoriy dasturchi
ushbu mavzuda yoritilgan daraxt tuzilmasi haqidagi bilimlarga ega bo’lishi shart.
96
6-qism. Ikkilik (binar) daraxt
Binar daraxtlar ma’lumotlar tuzilmalari ichida eng ko’p talab qilinadigan
tuzilmalardjan biri hisoblanadi, bu tuzilma ko’plab asosan hisoblash masalalari va
turli xil qidiruv tizimlarida keng qo’llaniladi. Ushbu mavzuda binar daraxtlarning
asosiy xarakteristikasi va binar daraxt tuzilmalari ustida bajariladigan turli xil
amallarni o’rganamiz.
Odatdagidek,
nazariy
ma’lumotlardan tashqari: binar daraxtlar
klassifikatsiyasi va binar daraxtlar ustida amallar bajarishning standart usullarini
qarab chiqamiz. Mavzuda binar daraxtlar ustida qo’llaniladigan algoritmlarning
Si va Python tillaridagi tadbiqini o’rganib chiqamiz.
Do'stlaringiz bilan baham: | 
