C Programming and Data Structures: Unit IV: a. Non-Linear Data Structures - Trees
C Programming Examples [Trees]
Non-Linear Data Structures
C Programming and Data Structures: Unit IV: a. Non-Linear Data Structures - Trees : Programming Examples
Programming Examples
Ex. 5.6.6 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. 5.6.7 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)));
}
if(x>y)
return x;
return y;
}
void inorder(bs *temp)
{
if(temp!= NULL)
{
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. 5.6.8 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 ();
int front, rear;
void insert(node *root,node *New)
{
if(New->data <root->data)
{
eals
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 ");
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
7 9 11 13
Ex. 5.6.9 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. 5.6.10 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 0
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))
equal(t1 -> right, t2->right);
{
/**************************************
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
C Programming and Data Structures: Unit IV: a. Non-Linear Data Structures - Trees : Tag: : Non-Linear Data Structures - C Programming Examples [Trees]
Related Topics
Related Subjects
C Programming and Data Structures
CS3353 3rd Semester EEE, ECE Dept | 2021 Regulation | 3rd Semester EEE Dept 2021 Regulation