C Programming Examples on Binary Trees

Programming Examples on Binary Trees

Ex.: 4.12.1: Program for counting and displaying leaf nodes. Sol. :

/************************************************************

Program For Printing And Counting The Leaf nodes Of The Binary Search Tree.

************************************************************/

#include<stdio.h>

#include <alloc.h>

#include<conio.h>

typedef struct bst1

{

int data;

struct bst1 *left,*right;

}bs;

bs *New,*second, *root;

/*-----------------------------------------------------

The main Function with a menu of operations

-----------------------------------------------------*/

void main()

{

char ans='N';

void insert(bs *,bs *);

void inorder(bs *);

int count(bs*,int);

int cnt;

bs *get_node();

clrscr();

root=NULL;

printf("\n\t Program For Displaying Leaf nodes of The Binary Search Tree");

do

{

New=get_node();

if(root == NULL)

root=New;

else

insert(root,New);

printf("\n Do u Want To enter More Elements?(y/n)");

ans=getch();

} while (ans=='y');

printf("\n The Tree Is: ");

inorder(root);

cnt=0;

printf("\n The Leaves in The Tree are: ");

cnt=count(root,cnt);

printf("\n The Total Number Of Leaf Nodes are: %d",cnt);

inorder(second);

}

bs *get_node()

{

bs *temp;

temp = (bs*)malloc(sizeof(bs));

printf("\n Enter The Element ");

scanf("%d",&temp->data);

temp->left=NULL;

temp->right=NULL;

return temp;

}

void insert(bs *root,bs *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

root->left=New;

else

insert(root->left, New);

}

if(New->data>root->data)

{

if(root->right== NULL)

root->right=New;

else

insert(root->right,New);

}

}

int count(bs* temp,int cnt)

{

static int i=0;

if(temp!= NULL)

{

if((temp->left== NULL)&&(temp->right==NULL))

{

printf("%d",temp->data);

i++;

return i;

}

else

{

count(temp->left,i);

count(temp->right,i);

}

}

}

void inorder(bs *temp)

{

if(temp!= NULL)

{

inorder(temp->left);

printf("%d",temp->data);

inorder(temp->right);

}

}

Output

Program For Displaying Leaf nodes of The Binary Search Tree

Enter The Element 10

Do u Want To enter More Elements? (y/n)

Enter The Element 8

Do u Want To enter More Elements? (y/n)

 Enter The Element 7

Do u Want To enter More Elements?(y/n)

 Enter The Element 9

Do u Want To enter More Elements?(y/n)

Enter The Element 12

Do u Want To enter More Elements?(y/n)

 Enter The Element 11

Do u Want To enter More Elements?(y/n)

 Enter The Element 13

Do u Want To enter More Elements?(y/n)

The Tree Is: 7 8 9 10 11 12 13

The Leaves in The Tree are: 79 11 13

The Total Number Of Leaf Nodes are: 4

Ex. 4.12.2: Program for counting total number of nodes.

Sol. :

/*************************************************************

Program For Counting Total number of nodes Of The Binary Search Tree.

*************************************************************/

#include<stdio.h>

#include <alloc.h>

#include<conio.h>

typedef struct bst1

{

int data;

struct bst1 *left,*right;

}bs;

bs *New,*root;

/*------------------------------------------------------

The main Function with a menu of operations

------------------------------------------------------*/

void main()

{

char ans='N';

void insert(bs *,bs *);

void inorder(bs *);

int count(bs *,int);

int cnt;

bs *get_node();

clrscr();

root=NULL;

printf("\n\t Program For The Binary Search Tree");

do

{

New=get_node();

if(root == NULL)

root=New;

else

insert(root,New);

printf("\n Do u Want To enter More Elements?(y/n)");

 ans=getch();

} while(ans=='y');

printf("\n The Tree Is: ");

inorder(root);

cnt=0;

cnt=count(root,cnt);

printf("\n The Total Number Of Nodes in Tree are: %d",cnt);

}

bs *get_node()

{

bs *temp;

temp=(bs*)malloc(sizeof(bs));

printf("\n Enter The Element ");

scanf("%d", &temp->data);

temp->left=NULL;

temp->right=NULL;

return temp;

}

void insert(bs *root,bs *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

}

root->left=New;

else

insert(root->left,New);

}

if(New->data>root->data)

{

if(root->right== NULL)

root->right=New;

else

insert(root->right,New);

}

}

int count(bs* temp,int cnt)

{

static int i=0;

if(temp!= NULL)

{

i++;

count(temp->left,i);

count(temp->right,i);

}

return i;

}

void inorder(bs *temp)

{

if(temp!= NULL)

{

inorder(temp->left);

printf("%d",temp->data);

inorder(temp->right);

}

}

Ex. 4.12.3 Program for finding height of BST.

Sol. :

/******************************************************

Program For finding height of Binary Search Tree.

*******************************************************/

#include<stdio.h>

#include <alloc.h>

#include <conio.h>

typedef struct bst1

{

int data;

struct bst1 *left, *right;

}bs;

bs *New,*root;

/*******************************************************

The main Function with a menu of operations

*******************************************************/

void main()

{

char ans='N';

void insert(bs *,bs *);

void inorder(bs *);

int height(bs *);

int count;

bs *get_node();

clrscr();

root = NULL;

printf("\n\t Program For The Binary Search Tree");

do

{

New=get_node();

if(root == NULL)

root=New;

else

insert(root,New);

printf("\n Do u Want To enter More Elements?(y/n)");

ans=getch();

} while(ans=='y');

printf("\n The Tree Is: ");

inorder(root);

count=0;

count=height(root);

printf("\n The height of Tree is : %d",count);

}

bs *get_node()

{

bs *temp;

temp=(bs*)malloc(sizeof(bs));

printf("\n Enter The Element ");

scanf("%d", &temp->data);

temp->left= NULL;

temp->right=NULL;

return temp;

}

void insert(bs *root,bs *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

root->left=New;

else

insert(root->left, New);

}

if(New->data>root->data)

{

if(root->right== NULL)

root->right=New;

else

insert(root->right, New);

}

}

int height(bs *temp)

{

int max(int,int);

if (temp== NULL)

return 0;

else

return (1+max(height(temp->left), height(temp->right)));

}

int max(int x, int y)

{

if(x>y)

return x;

return y;

}

void inorder(bs *temp)

{

if(temp!= NULL)`1

{

inorder(temp->left);

printf("%d",temp->data);

inorder(temp->right);

}

}

Program For The Binary Search Tree

Enter The Element 10

Do u Want To enter More Elements?(y/n)

 Enter The Element 9

Do u Want To enter More Elements?(y/n)

 Enter The Element 15

Do u Want To enter More Elements?(y/n)

Enter The Element 7

Do u Want To enter More Elements?(y/n)

Enter The Element 12

Do u Want To enter More Elements?(y/n)

 Enter The Element 18

Do u Want To enter More Elements?(y/n)

 Enter The Element 14

Do u Want To enter More Elements?(y/n)

 Enter The Element 13

Do u Want To enter More Elements? (y/n)

The Tree Is 7 9 10 12 13 14 15 18

The height of Tree is : 5

Ex. 4.12.4: Program to display the tree in levelwise manner.

Sol. :

/***************************************************************

Program to create a binary tree and print the data level wise or in a breadth first search order. The data in each level will be

displayed on seperate lines.

***************************************************************

#include<stdio.h>

#include <alloc.h>

#include <conio.h>

#define size 50

typedef struct node

{

int data;

struct node *left;

struct node *right;

}btree;

btree *root, *New;

void insert(node *,node *);

void enque(btree *Node);

btree *deque ();

btree *que[size];

int front,rear;

void insert(node *root,node *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

root->left=New;

else

insert(root->left,New);

}

if(New->data>root->data)

{

if(root->right == NULL)

root->right=New;

else

insert(root->right,New);

}

}

void display()

{

btree *temp, *dummy;

dummy=(btree*)malloc(sizeof(btree));

if (dummy==NULL)

printf("Insufficient Memory\n");

dummy->left = root;

dummy->right = NULL;

dummy->data = '';

temp = dummy ->left;

enque(temp);

enque(dummy);

temp = deque();

while (front != rear)

{

if (temp!= dummy)

{

printf("%d",temp->data);

if (temp ->left != NULL)

enque(temp -> left);

if (temp->right != NULL)

enque(temp -> right);

}

else

{

enque(temp);

printf("\n");

}

temp=deque();

}

}

void enque(btree *Node)

{

if (rear == size-1)

printf("Queue is full\n");

rear rear + 1;

que[rear]=Node;

}

btree *deque ()

{

btree *Node;

if (front == rear)

printf("Queue is empty\n");

front++;

Node = que [front];

return(Node);

}

void main()

{

char ans='y';

root=NULL;

front-rear=-1;

do

{

clrscr();

New (btree *)malloc(sizeof(btree));

New->left=NULL;

New->right=NULL;

printf("\n Enter The Element ");

scanf("%d", &New->data);

if(root == NULL)/* Tree is not Created */

root=New;

else

insert(root,New);

printf("\n Do u Want To enter More Elements?(y/n)\n");

ans=getch();

} while(ans=='y');

display();

getch();

}

Output

Enter The Element 10

Do u Want To enter More Elements?(y/n)

Enter The Element 8

Do u Want To enter More Elements?(y/n)

Enter The Element 7

Do u Want To enter More Elements?(y/n)

Enter The Element 9

Do u Want To enter More Elements?(y/n)

Enter The Element 12

Do u Want To enter More Elements? (y/n)

 Enter The Element 11

Do u Want To enter More Elements? (y/n)

Enter The Element 13

Do u Want To enter More Elements?(y/n)

10

8 12

79 11 13

Ex. 4.12.5 Program for copying binary search tree.

Sol. :

/***************************************************

Program For Copying The Binary Search Tree.

**************************************************/

#include<stdio.h>

#include <alloc.h>

#include <conio.h>

typedef struct bst1

{

int data;

struct bst1 *left,*right;

}bs;

bs *New,*second, *root;

/***********************************************************

The main Function with operations

************************************************************

void main()

{

char ans='N';

void insert(bs *,bs *);

void inorder(bs *);

bs *copy(bs *);

bs *get_node();

clrscr();

root = NULL;

printf("\n\t Program For Copying The Binary Search Tree");

do

{

New=get_node();

if(root == NULL)

root=New;

else

insert(root,New);

printf("\n Do u Want To enter More Elements?(y/n)");

ans=getch();

}while(ans=='y');

printf("\n The Tree Is: ");

inorder(root);

printf("\n The Copied Tree Is :");

second copy(root);

inorder(second);

}

bs *get_node()

{

bs *temp;

temp=(bs*)malloc(sizeof(bs));

printf("\n Enter The Element ");

scanf("%d", &temp->data);

temp->left=NULL;

temp->right=NULL;

return temp;

void insert(bs *root,bs *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

root->left=New;

else

insert(root->left, New);

}

if(New->data>root->data)

{

if(root->right== NULL)

root->right=New;

else

insert(root->right,New);

}

}

bs *copy(bs * first)

{

bs *New;

if (first!= NULL)

{

New = (bs *)malloc(sizeof(bs));

if (New == NULL)

printf("\nMemory Is Not Allocated\n");

New->left copy(first -> left);

New->right=copy(first -> right);

New->data = first -> data;

return (New);

}

else

return NULL;

}

void inorder(bs *temp)

{

if(temp!= NULL)

{

inorder(temp->left);

printf("%d", temp->data);

inorder(temp->right);

}

}

Output

Program For Copying The Binary Search Tree

 Enter The Element 10

Do u Want To enter More Elements? (y/n)

Enter The Element 8

Do u Want To enter More Elements?(y/n).

 Enter The Element 9

Do u Want To enter More Elements?(y/n)

 Enter The Element 7

Do u Want To enter More Elements?(y/n)

 Enter The Element 15

Do u Want To enter More Elements?(y/n)

The Tree Is 7 8 9 10 15

The Copied Tree Is 7 8 9 10 15

Ex. 4.12.6: Program for comparing two BSTs.

Sol. :

/*************************************************************

Program For Comparision Of Two Binary Search Trees.

*************************************************************/

#include<stdio.h>

#include <conio.h>

#define TRUE 1

#define FALSE O

typedef struct bst1

{

int data;

struct bst1 *left,*right;

}bs;

bs *s;

void insert(bs *,bs *);

void inorder(bs *);

int equal(bs *,bs *);

bs *get_node();

/*****************************************************

This Function is for allocation of memory for the node

*****************************************************/

bs *get_node()

{

bs *temp;

temp=new bs;

printf("\n Enter The Element ");

scanf("%d", &temp->data);

temp->left=NULL;

temp->right=NULL;

return temp;

}

/*******************************************************

This function is for creating a binary search tree

*******************************************************//

void insert(bs *root,bs *New)

{

if(New->data <root->data)

{

if(root->left== NULL)

root->left=New;

else

insert(root->left,New);

}

if(New->data>root->data)

{

if(root->right == NULL)

root->right=New;

else

insert(root->right,New);

}

}

/***********************************************************

This function displays the tree in inorder fashion

*********************************************************/

void inorder(bs *temp)

{

if(temp!= NULL)

{

inorder(temp->left);

printf("%d",temp->data);

inorder(temp->right);

/**********************************************************

Function For Comparing Two Trees

**********************************************************/

int equal(bs *t1,bs *t2 )

{

int flag;

 flag=FALSE;

if (t1 == NULL && t2 == NULL)

flag:=TRUE;

else

if (t1 != NULL && t2 != NULL)

if (t1->data == t2 -> data)

if (equal(t1 -> left, t2 -> left))

flag= equal(t1 -> right, t2->right);

return(flag);

}

/**********************************************************

The main Function

**********************************************************/

void main()

{

int choice,flag;

bs *root1, *root2;

char ans='N';

clrscr();

root1=NULL;

root2= NULL;

printf("\n\t Program For Comparing The Two Binary Search Trees");

printf("\nCreate First Tree");

do                   

{

s=get_node();

if(root1== NULL)

root1=s;

else

insert(root1,s);

printf("\n Do u Want To enter More Elements?(y/n)");

ans=getch();

}while(ans=='y');

printf("\nCreate Second Tree");

do

{

s=get_node();

if(root2== NULL)

root2=s;

else

insert(root2,s);

printf("\n Do u Want To enter More Elements?(y/n)");

 ans=getch();

} while(ans=='y');

printf("\n First Tree");

inorder(root1);

printf("\nSecond Tree");

inorder(root2);

flag equal(root1,root2);

if (flag==TRUE)

printf("\nThe two trees are identical \n");

else

printf("\nThe two trees are not identical \n");

getch();

 Output

Program For Comparing The Two Binary Search Trees

Create First Tree

Enter The Element 10

Do u Want To enter More Elements?(y/n)

Enter The Element 8

Do u Want To enter More Elements? (y/n)

 Enter The Element 7

Do u Want To enter More Elements?(y/n)

Enter The Element 9

Do u Want To enter More Elements?(y/n)

Enter The Element 12

Do u Want To enter More Elements?(y/n)

 Create Second Tree

Enter The Element 10

Do u Want To enter More Elements?(y/n)

 Enter The Element 8

Do u Want To enter More Elements?(y/n)

Enter The Element 5

Do u Want To enter More Elements?(y/n)

 Enter The Element 9.

Do u Want To enter More Elements?(y/n)

 Enter The Element 12

Do u Want To enter More Elements? (y/n)

First Tree 7 8 9 10 12

Second Tree 5 8 9 10 12

The two trees are not identical