Binary Search Tree (BST)
A BST is a binary tree in symmetric order.
It is also called as ordered or sorted binary tree.
The basic idea behind this data structure to have such a storing repository that provides the efficient way of
A BST is a binary tree in symmetric order.
It is also called as ordered or sorted binary tree.
The basic idea behind this data structure to have such a storing repository that provides the efficient way of
- Data sorting.
- Searching.
- Retriving.
A BST is a binary tree where nodes are ordered in the following way:
- Each node contains one key (also known as data)
- The keys in the left subtree are less then the key in its parent node, in short L < P;
- The keys in the right subtree are greater the key in its parent node, in short P < R;
- Duplicate keys are not allowed.
The following operation can be made on the BST.
- Insertion
- Searching
- Sorting.
- Traversing.
- Deletion.
Below mentioned program describes insertion, searching , deletion and inorder traversal ( recursive and non-recursive) in BST.
/* Program to demonstrate the Binary tree inorder traversal with both recursion and without recursion ( using stack ) */
/* Program to demonstrate the Binary tree inorder traversal with both recursion and without recursion ( using stack ) */
/* BST - Binary
search tree */
#include <stdio.h>
#include <stdlib.h>
/* Binary search tree
structure */
struct btree{
int data;
struct
btree *pLeft;
struct
btree *pRight;
};
/* Stack structure
Used for non recursive implementation of
inorder function */
Used for deletion of BST */
*/
struct stack{
struct
btree *sNode;
struct
stack *nNode;
};
/* Global array to be
inserted in BST */
int dataArray[] =
{5,3,1,2,7,6,10,4};
/* -- Functions definition -- */
/* Function to insert
node into BST */
void insertTreeNode(struct btree **pNode, int
nVal);
/* Function to
traverse inorder - recursion */
void inorderTree(struct btree *pNode);
/*Function to delete
all nodes of BST */
void freeMemory(struct btree **pNode);
/* Stack function -
Push and Pop*/
void pushNode(struct stack **top, struct
btree *pNode);
struct btree *popNode(struct stack **top);
/* Function to
implement inorder using stack - Non recursion */
void
inorderWithStack(struct btree *pNode);
/* Function to check
stack empty */
int isStackEmpty(struct stack *top);
/* Counting number of
nodes in BST */
int countNodes (struct btree *pNode);
/* Search for a key
in BST */
struct btree
*searchKeyLocation( struct btree *pNode, int key);
/* Function to delete
a node from BST */
void deleteNode(struct btree *pNode, int
val);
/* Main program */
int main(void){
struct
btree *node = NULL;
int i;
int data =
0;
int
numElement = sizeof(dataArray)/sizeof(dataArray[0]);
struct
btree *keyLocation = NULL;
for(i = 0;
i < numElement; i++)
insertTreeNode(&node,
dataArray[i]);
inorderWithStack(node);
//inorderTree(node);
printf("\nNumber
of nodes: %d", countNodes(node));
keyLocation = searchKeyLocation(node, 10);
if(keyLocation
!= NULL){
printf("\nFound
location: 0x%x %d", keyLocation, *keyLocation);
}else
printf("\nLocation
not found ..");
printf("Enter
the value to be deleted: ");
scanf("%d",
&data);
deleteNode(node,data);
inorderWithStack(node);
getch();
return 0;
}
/* -- Function
definitions -- */
void insertTreeNode(struct btree **pNode, int
nVal){
if(*pNode
== NULL){
*pNode = (struct
btree *)malloc(sizeof(struct
btree));
if(*pNode
== NULL){
printf("\nMemory
is not present...!");
exit(0);
}else{
(*pNode)->pLeft = NULL;
(*pNode)->pRight = NULL;
(*pNode)->data = nVal;
}
}else{
if((*pNode)->data
> nVal)
insertTreeNode(&(*pNode)->pLeft, nVal);
else
insertTreeNode(&(*pNode)->pRight, nVal);
}
}
void inorderTree(struct btree *pNode){
if(pNode!=NULL){
inorderTree(pNode->pLeft);
printf("%d\t",
pNode->data);
inorderTree(pNode->pRight);
}
}
void
inorderWithStack(struct btree *pNode){
int done =
0;
struct
stack *top = NULL;
if(pNode
== NULL){
printf("\nBinary
tree is empty ..!");
return;
}
while(!done){
if(pNode
!= NULL){
/* Push
the node in stack */
pushNode(&top, pNode);
pNode = pNode->pLeft;
}else{
if(!isStackEmpty(top)){
pNode = popNode(&top);
printf("%d\t", pNode->data);
pNode = pNode->pRight;
}else{/* if stack becomes empty */
done = 1;
}
}
} /* While loop
finishes */
}
void pushNode(struct stack **top, struct
btree *pNode){
int iData =
0;
struct
stack *temp = (struct stack *)malloc(sizeof(struct
stack));
if(temp ==
NULL){
printf("\nMemory
not available..");
return;
}
temp->sNode = pNode;
temp->nNode = (*top);
(*top) = temp;
}
struct btree *popNode(struct stack **top){
struct
btree *retNode = NULL;
if(*top ==
NULL){
printf("\nStack
is empty..");
return
NULL;
}
retNode = (*top)->sNode;
(*top) = (*top)->nNode;
return
retNode;
}
int isStackEmpty(struct stack *top){
return
(top == NULL)?1:0;
}
int countNodes (struct btree *pNode){
if(pNode ==
NULL)
return
0;
else if(pNode->pLeft == NULL &&
pNode->pRight == NULL)
return
1;
else
return
(1 + countNodes(pNode->pLeft) + countNodes(pNode->pRight));
}
struct btree
*searchKeyLocation( struct btree *pNode, int key){
if(pNode ==
NULL){
printf("\nBinary
tree is empty..");
return
NULL;
}
while(pNode
!= NULL){
if(pNode->data
== key)
return
pNode;
else if(pNode->data > key)
pNode = pNode->pLeft;
else
pNode = pNode->pRight;
}
return
NULL;
}
void freeMemory(struct btree **pNode){
int done
= 0;
struct
stack *top = NULL;
struct
btree *temp = NULL;
if(*pNode
== NULL){
printf("\nBinary
tree is empty ..");
return;
}
while(!done){
if(*pNode!=NULL){
pushNode(&top,(*pNode));
(*pNode) = (*pNode)->pLeft;
}else{
if(!isStackEmpty(top)){
(*pNode) = popNode(&top);
temp = (*pNode);
(*pNode) = (*pNode)->pRight;
free(temp);
temp = NULL;
}else{
done = 1;
}
}
} /* While loop
ends here */
}
void deleteNode(struct btree *pNode, int
val){
struct
btree *prev = NULL;
struct
btree *cur = pNode;
struct
btree *anj;
struct
btree *ver;
while(cur!=NULL
&& cur->data !=val){
prev = cur;
if(val
> cur->data)
cur = cur->pRight;
else
cur = cur->pLeft;
}
if(cur==NULL){
printf("NOT
FOUND");
}else{
printf("Deleting
%d \n",cur->data);
/* Two
children */
if(cur->pLeft
&& cur->pRight ){
anj = cur->pRight;//move pRight
ver = cur;//previous
//if
moving to extreme pLeft is not possible
if(anj->pLeft
== NULL){
cur->data = anj->data;
cur->pRight =
anj->pRight;
free(anj);
}else{
//move
to extreme pLeft
while(anj->pLeft!=NULL){
ver = anj;
anj = anj->pLeft;
}
cur->data =
anj->data;
ver->pLeft=NULL;
free(anj);
}
}else{
// Only
pRight
if(cur->pRight!=NULL
&& cur->pLeft==NULL){
prev->pRight =
cur->pRight;
free(cur);
return;
//only
pLeft
}else
if(cur->pRight==NULL &&
cur->pLeft!=NULL){
prev->pLeft=cur->pLeft;
free(cur);
}else{
if(cur->data
> prev->data)
prev->pRight =
NULL;
else
prev->pLeft = NULL;
free(cur);
}
}
}
}
No comments:
Post a Comment