How we can create a BST ?
For creating a BST(Binary search tree), we create a node that have a data,leftchild and rightchild pointer.
-leftchild hold the address of root of left subtree.
-rightchild hold the address of root of right subtree.
program-
#include< stdio.h>
#include< conio.h>
#include< alloc.h>
struct node
{
int data;
struct node *leftchild;
struct node *rightchild;
};
struct node *root=NULL;
void insert(int data)
{
struct node *tempNode=(struct node*)malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data=data;
tempNode->leftchild=NULL;
tempNode->rightchild=NULL;
if(root==NULL)
{
root=tempNode;
}
else
{
current=root;
parent=NULL;
while(1)
{
parent=current;
if(data< parent->data){
current=current->leftchild;
if(current==NULL)
{
parent->leftchild=tempNode;
return;
}
}
else
{
current=current->rightchild;
if(current==NULL)
{
parent->rightchild=tempNode;
return;
}
}
}
}
}
void traverse(struct node *root)
{
if(root!=NULL)
{
traverse(root->leftchild);
printf("%d ",root->data);
traverse(root->rightchild);
}
}
void main()
{
clrscr();
insert(3);
insert(1);
insert(4);
insert(2);
insert(5);
printf("In-order traversal of BST is :\n");
traverse();
getch();
}
In-order traversal of BST is :
1 2 3 4 5