Binary Search Tree
Implement a C program to construct a Binary Search Tree and also display the elements in the tree using Inorder , Preorder and Postorder traversals.
Create a structure
struct tnode
{
int data;
struct tnode * leftc;
struct tnode * rightc;
};
Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
Input and Output Format:
Refer Sample Input and Output for formatting specifications.
[All text in bold corresponds to input and the rest corresponds to output]
Sample Input and Output:
Enter the element to be inserted in the tree
1
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
2
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
3
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
4
Do you want to insert another element?
no
Inorder Traversal : The elements in the tree are 1 2 3 4
Preorder Traversal : The elements in the tree are 1 2 3 4
Postorder Traversal : The elements in the tree are 4 3 2 1
Code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct tnode {
int data;
struct tnode * leftc;
struct tnode * rightc;
};
void insert(struct tnode
**, int num);
void inorder(struct tnode
*);
void preorder(struct tnode
*);
void postorder(struct
tnode *);
int main() {
struct tnode * root=NULL;
char ch[5];
int num;
do {
printf("Enter the element to be inserted in
the tree\n");
scanf("%d",&num);
insert(&root, num);
printf("Do you want to insert another
element?\n");
scanf("%s",ch);
}while(strcmp(ch,"yes")==0);
printf("Inorder Traversal : The elements in the tree
are");
inorder(root);
printf("\n");
printf("Preorder Traversal : The elements in the tree
are");
preorder(root);
printf("\n");
printf("Postorder Traversal : The elements in the tree
are");
postorder(root);
printf("\n");
return 0;
}
void insert(struct tnode
** s, int num) {
if(*s==NULL)
{
(*s)=(struct tnode
*)malloc(sizeof(struct tnode));
(*s)->data=num;
(*s)->leftc=NULL;
(*s)->rightc=NULL;
}
else
{
if((*s)->data>num)
insert(&(*s)->leftc,num);
else
insert(&(*s)->rightc,num);
}
}
void inorder(struct tnode
* s) {
if(s==NULL)
return;
else
{
inorder(s->leftc);
printf(" %d",s->data);
inorder(s->rightc);
}
}
void preorder(struct tnode
* s) {
if(s==NULL)
return;
else
{
printf(" %d",s->data);
preorder(s->leftc);
preorder(s->rightc);
}
}
void postorder(struct
tnode * s) {
if(s==NULL)
return;
else
{
postorder(s->leftc);
postorder(s->rightc);
printf(" %d",s->data);
}
}
Search Operation:
int search(struct tnode *
s, int ele) {
if(s==NULL)
return 0;
else
{
if(ele==s->data)
return 1;
else if(ele< s->data)
return search(s->leftc,ele);
else
return search(s->rightc,ele);
}
}
Find the size of the
tree:
int findSize(struct tnode
* s) {
if(s==NULL)
return 0;
else
return(findSize(s->leftc)+findSize(s->rightc)+1);
}
Finding maximum depth:
int findMaxDepth(struct tnode * s) {
if(s==NULL)
return 0;
else
{
int
left=findMaxDepth(s->leftc);
int
right=findMaxDepth(s->rightc);
if(left>right)
return (left+1);
else
return (right+1);
}
}
Please do comment If u have any Queries!
No comments:
Post a Comment