Daraxtsimon tuzilmalar

Binar daraxt bo’yicha qidiruv funksiyasi
Mazkur funksiyaning vazifasi shundan iboratki, u berilgan 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 4.7- rasmdagidek bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shoxga ega), masalan:
Berilgan binar daraxtning terminal tugunlari balandliklarini aniqlash algoritmi va dasturini keltiring.
#include
#include
using namespace std;
class node{
public: int info;
node *left;
node *right;
};
int k=0;
int height(node *tree){
int h1,h2;
if (tree==0) return (-1);
else {
h1 = height(tree->left);
h2 = height(tree->right);
if (h1>h2) return (1 + h1);
else return (1 + h2);
}}
node *new_tree(int *arr, int start, int end)
{
if(start>end) return 0;
else {
int mid=(start+end)/2;
node *tree=new node;
tree->info=arr[mid];
tree->left=new_tree(arr,start,mid-1);
tree->right=new_tree(arr,mid+1,end);
return tree;
}
}
void vizual(node *tree,int l)
{ int i;
if(tree!=0) {
vizual(tree->right,l+1);
for (i=1; i<=l; i++) cout<<" ";
cout<info<vizual(tree->left,l+1);
}
}
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;
p->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<cout<<"\nya'ni\n";
vizual(tree,0);
int h=height(tree);
cout<<"balandligi="<getch();
}





Xulosa
Xulosa qilib shuni aytishim mumkinki daraxtning balandligini aniqlashni o’rganganimizdan keyin uning muvoza-natlanganligini tekshirish mumkin. Binar daraxtning muvozanatlanganligini tekshirish uchun uning har bir tugunini har ikkala qism daraxti balandliklarini hisoblab, farqlarini tekshirib ko’rish kerak. Agar farq 0 yoki 1 ga teng bo’lsa, bu muvozanatlangan daraxt hisoblanadi. Quyida binar daraxtni muvozanatlanganlikka tekshirishning rekursiv funksiyasini qo’llovchi dastur keltirilgan.