BINARY SEARCH TREE:
1.Implement binary search tree (BST) to perform a following operation:
i) BST - copy and mirror image of BST,
Counting leaf node , non leaf node , total nodes
//assignment 2:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left,*right;
}BST;
BST *create();
BST *insert(BST *,int);
BST *preorder(BST *);
int totalnodes(BST *);
int leafnodes(BST *);
int nonleafnodes(BST *);
BST * mirrorimage(BST *);
static int count=0;
int main ()
{
int ch,x,m;
BST *root=NULL,*ans,*mirror;
do
{
printf("\n1:create\n2:insert\n3:preorder");
printf("\n4:Total_Nodes\n5:leaf_count\n6:non_leaf_nodes");
printf("\n7:mirror_image");
printf("\n\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:root=create();
break;
case 2:printf("enter the data to be inserted:");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:printf("\nDISPLAY:\n");
preorder(root);
break;
case 4:
count=totalnodes(root);
if(count==0)
printf("\n no nodes in the tree!");
else
printf("total no. of nodes are %d",count);
break;
case 5:
count=leafnodes(root);
if(count==0)
printf("\n no leaf nodes in the tree!");
else
printf("total no of leaf nodes are %d",count);
break;
case 6:
count=nonleafnodes(root);
if(count==0)
printf("\n no non leaf nodes in the tree!");
else
printf("total no of non leaf nodes are %d",count);
break;
case 7:printf("\noriginal tree:\n");
preorder(root);
mirror=mirrorimage(root);
printf("\nThe mirror tree:\n");
preorder(mirror);
break;
default:printf("\nInvalid Case!!!\n");
}
}while(ch!=0);
}
BST *create()
{
BST *root=NULL;
int x,i,n;
printf("enter the nodes to be created:");
scanf("%d",&n);
printf("\nenter the data:");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}
BST *insert(BST *tree,int x)
{
BST *newnode;
if(tree==NULL)
{
newnode=(BST *)malloc(sizeof(BST));
newnode->data=x;
newnode->left=NULL;
newnode->right=NULL;
return(newnode);
}
if(x<tree->data)
{
tree->left=insert(tree->left,x);
return(tree);
}
else if(x>tree->data)
{
tree->right=insert(tree->right,x);
return(tree);
}
else
printf("\nduplicate data");
return(tree);
}
BST *preorder(BST *tree)
{ // root-left-right
if(tree!=NULL)
{
printf("%d\n",tree->data);
preorder(tree->left);
preorder(tree->right);
}
}
int totalnodes(BST *root)
{
if(root==NULL)
return 0;
else
{
return ( 1 + totalnodes(root->left) + totalnodes(root->right) );
}
}
int leafnodes(BST *root)
{
if(root==NULL)
{
return 0;
}
else if(root->left==NULL && root->right==NULL)
return 1;
else
return leafnodes(root->left) + leafnodes(root->right);
}
int nonleafnodes(BST *root)
{
if(root==NULL)
{
return 0;
}
if(root->left==NULL && root->right==NULL)
return 0;
else
return (1 + nonleafnodes(root->left) + nonleafnodes(root->right) );
}
BST * mirrorimage(BST *root)
{
BST * temp=root;
if(temp!=NULL)
{
temp=root->left;
root->left=mirrorimage(root->right);
root->right=mirrorimage(temp);
}
return(root);
}
output:
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:1
enter the nodes to be created:5
enter the data:10
5
20
15
25
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:3
DISPLAY:
10
5
20
15
25
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:4
total no. of nodes are 5
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:5
total no of leaf nodes are 3
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:6
total no of non leaf nodes are 2
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
enter your choice:7
original tree:
10
5
20
15
25
The mirror tree:
10
20
25
15
5
1:create
2:insert
3:preorder
4:Total_Nodes
5:leaf_count
6:non_leaf_nodes
7:mirror_image
ii) Level - order traversal of binary search tree using queue:
// Recursive C program for level
// order traversal of Binary Tree
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
struct node {
int data;
struct node *left, *right;
};
/* Function prototypes */
void printCurrentLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printCurrentLevel(root, i);
}
/* Print nodes at a current level */
void printCurrentLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1) {
printCurrentLevel(root->left, level - 1);
printCurrentLevel(root->right, level - 1);
}
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node == NULL)
return 0;
else {
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);
/* use the larger one */
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);
return 0;
}
output:
Level Order traversal of binary tree is
1 2 3 4 5
.
Great program bro
ReplyDeletethanks bro...
Delete