Implement Binary Search Tree using List C Programming.
A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with value less than the parent node; the right sub-tree contains only nodes with value greater than or equal to the parent node.
The BST data structure is the basis for a number of highly efficient sorting and searching algorithms, and it can be used to construct more abstract data structures including sets, multisets, and associative arrays.
Tree Traversal:
Displaying (or) visiting order of nodes in a tree is called as Tree Traversal. There are three types tree traversals:
- In - Order Traversal
- Pre - Order Traversal
- Post - Order Traversal
1) In-Order Traversal(Left, Root, Right)
In In-Order traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This in-order traversal is applicable for every root node of all sub-trees in the tree.
i.e
- Traverse the left subtree in inorder
- Process the root Node
- Traverse the right subtree in inorder
2) Pre-Order Traversal( Root,Left, Right)
In Pre-Order traversal, the root node is visited first, then its left child and later its right child. This pre-order traversal is applicable for every root node of all sub-trees in the tree.
- e.
- Process the root Node
- Traverse the left subtree in preorder
- Traverse the right subtree in preorder
3) Post-Order Traversal( Left, Right, Root)
In Post-Order traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited.
i.e
- Traverse the left subtree in postorder
- Traverse the right subtree in Postorder
- Process the root Node
#include<stdio.h> #include<conio.h> #include<stdlib.h>
struct BST
{
int info;
struct BST *llink,*rlink;
};
typedef struct BST node;
node *create(node *root,int ele)
{
node *temp,*prev,*cur; temp=(node *)malloc(sizeof(node)); temp->info=ele;
temp->llink=NULL; temp->rlink=NULL; if(root==NULL)
return temp; prev=NULL; cur=root; while(cur!=NULL)
{
prev=cur; if(ele<cur->info)
cur=cur->llink;
else
cur=cur->rlink;
}
if(ele<prev->info)
prev->llink=temp;
else
prev->rlink=temp;
return root;
}
void preorder(node *root)
{
if(root==NULL) return;
printf("%d ",root->info); preorder(root->llink); preorder(root->rlink);
}
void inorder(node *root)
{
if(root==NULL) return;
inorder(root->llink); printf("%d ",root->info); inorder(root->rlink);
}
void postorder(node *root)
{
if(root==NULL) return;
postorder(root->llink); postorder(root->rlink); printf("%d ",root->info);
}
int main()
{
node *root=NULL; int ch,ele; while(1)
{
printf("\n 1: Create 2: Preorder 3:Inorder 4: Postorder 5:exit:"); printf("\n Enter your choice:");
scanf("%d",&ch); switch(ch)
{
case 1:
case 2:
case 3:
case 4:
case 5:
}
}
printf("\n Enter the element to be inserted:"); scanf("%d",&ele);
root=create(root,ele); break;
preorder(root); break;
inorder(root); break;
postorder(root); break;
exit(0);
getch(); return 0;
}
