all about binary tree !!


I recently implemented few of the operations on the binary tree. Some of the operations might match with my previous posts. I have simply posted the code. Please come up with queries if any.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
long long test;
using namespace std;
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
int flag=0;
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{ p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL )
{
temp= q;
if( val >= temp->data)
q=temp->right;
else
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
temp->right =n;
else
temp->left = n;
}
return p;
}
int count1 ( struct tnode *p)
{ int c1=0;
int c2=0;
if( p != NULL){
c1=count1(p->left);
c2= count1(p->right);
return 1+c1+c2;
}
}
struct tnode *delmin(struct tnode *p)
{
struct tnode *temp=p;
while( temp->left->left != NULL)
{
temp = temp->left;
}
temp->left=NULL;
delete(temp->left);
return p;
}
struct tnode *delmax(struct tnode *p)
{
struct tnode *temp=p;
while( temp->right->right != NULL)
{
temp = temp->right;
}
temp->right=NULL;
delete(temp->right);
return p;
}
int height(struct tnode *p)
{
int h1=0;
int h2=0;
if (p == NULL)
return 0;
if(p->left)
h1= height(p->left);
if(p->right)
h2= height(p->right);
return (1+max(h1,h2));
}
bool iscomptree(struct tnode *p)
{
struct tnode *temp=p;
int l,h;
l=count1(p);
h=height(temp);
int t;
t=(int) (pow(2,((float)h))-1);
if(t == l)
return true;
else
return false;
}
struct tnode *mirror(struct tnode *p)
{
if(p == NULL)
return p ;
else
{
mirror(p->left);
mirror(p->right);
struct tnode *temp;
temp=p->left;
p->left=p->right;
p->right=temp;
}
return p;
}
bool identical(struct tnode* a, struct tnode* b)
{
if (a==NULL && b==NULL){return(true);}
else if (a!=NULL && b!=NULL)
{
return(a->data == b->data &&
identical(a->left, b->left) &&
identical(a->right, b->right));
}
else return(false);
}
int check( struct tnode *p)
{ int h1,h2,sum=0;
if(p != NULL)
{
if(p->left && ! (p->right) || p->right && !(p->left))
{
flag=1;
return flag;
}
else{
if(flag != 1)
{
flag= check(p->left);
flag=check(p->right);
}
}
}
return flag;
}
int add ( struct tnode *p)
{ int sum1=0, sum2=0 ;
if( p != NULL){
sum1=add(p->left);
sum2=add(p->right);
return sum1+sum2+p->data;
}
}
void inorder ( struct tnode *p)
{
if( p != NULL){
inorder(p->left);
printf("%d\t",p->data);
inorder(p->right);
}
}
void preorder ( struct tnode *p)
{
if( p != NULL){
printf("%d\t",p->data);
preorder(p->left);
preorder(p->right);
}
}
void postorder ( struct tnode *p)
{
if( p != NULL){
postorder(p->left);
postorder(p->right);
printf("%d\t",p->data);
}
}
main()
{
struct tnode *root=NULL;
root=insert(root,16);
root=insert(root,14);
root=insert(root,20);
root=insert(root,12);
root=insert(root,15);
root=insert(root,18);
root=insert(root,22);
printf("Inorder traversal of the tree\n");
inorder(root);
cout<<endl;
printf("Preorder traversal of the tree\n");
preorder(root);
cout<<endl;
printf("Postorder traversal of the tree\n");
postorder(root);
cout<<endl;
printf("Height of the binary tree : ");
cout<<height(root)-1;
cout<<endl;
printf("Strictly binary tree[=0]: ");
cout<<check(root);
cout<<endl;
printf("Complete binary tree[=1]: ");
cout<<iscomptree(root);
cout<<endl;
struct tnode *r;
cout<<endl;
root=delmin(root);
inorder(root);
root=delmax(root);
cout<<endl;
inorder(root);
}

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: