17. Muvozanatlangan binar daraxtlar

1. 
   B.
   

4.10-rasm. A – binar daraxt; b – binar daraxtning ekranda namoyon bo’lishi

Yuqorida keltirilgan bir nechta algoritmlarni qo’llab bitta misol ko’rib chiqamiz.

Misol: berilgan binar daraxtning balandligini aniqlang va muvozanatlang.

Dastur kodi

#include

#include

Using namespace std;

Class node{

Public: int info;

Node *left;

Node *right;

};

Int k=0;

Int intrave(node *tree){

If (tree!=NULL){int a=NULL, b=NULL;

If (tree->left!=NULL){ a=tree->left->info; }

If (tree->right!=NULL){ b=tree->right->info; }

Cout»<’ngida=>»<

Intrave(tree->left);

Intrave(tree->right); }

Return 0;

}

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);

}

}

Int create_arr(node *tree,int *arr){

If(!tree) return 0;

Else{

Create_arr(tree->left,arr);

Arr[k++]=tree->info;

Create_arr(tree->right,arr);

}

}

Node *new_tree(int *arr, int start, int end)

{

If(start>end) return NULL;

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!=NULL) {

Vizual(tree->right,l+1);

For (i=1; i<=l; i++) cout<<» «;

Cout

Vizual(tree->left,l+1);

}

}

Int main()

{ int n,key,s; node *tree=NULL,*next=NULL;

Cout<<»n=»; cin>>n; int arr[n];

For(int i=0; i

Node *p=new node;

Node *last=new node;

Cin>>s;

p->info=s;

p->left=NULL;

p->right=NULL;

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==NULL)break; }

If(p->infoinfo)last->left=p;

Else last->right=p;}

Cout<

Intrave(tree);

Cout<<»\nya'ni\n»;

Vizual(tree,0);

Int h=height(tree);

Cout<<»balandligi=»<