Binary Search Tree : Binary search tree is a tree in which the left descendant has data lower than the node and the right descendant has data greater than the node. A binary search tree has several applications. It can be used to detect duplicates, sort a list, efficient search and delete the items. The inorder traversal of a binary search tree prints the elements in increasing order.
C program implementing binary search tree.
C program implementing binary search tree.
//Binary Search Tree /** * *@author VIKASH VIK VIKKU VIKASHVVERMA * */ #include<stdio.h> typedef struct node { int data; struct node*left; struct node*right; }node; //insert node in a binary search tree void insert(node**bst,int n) { if(*bst==NULL)//if node is NULL than create a node { *bst=(node*)malloc(sizeof(node)); (*bst)->data=n; (*bst)->left=NULL; (*bst)->right=NULL; } else { //if number is less than node data than insert in left subtree if(n<(*bst)->data) insert(&((*bst)->left),n); else//insert in right subtree insert(&((*bst)->right),n); } } //search for a parent node and node to be deleted void search(node**bst,node**par,node**del,int*found,int n) { node*temp=*bst; if(temp==NULL) { *found=0; return; } *par=NULL; while(temp!=NULL) { if(temp->data==n) { *del=temp; *found=1; return; } *par=temp; if(n<temp->data) temp=temp->left; else temp=temp->right; } } //delete a node and adjust the binary search tree void delete(node**bst,int n) { node*par=NULL,*del=NULL,*par1=NULL,*del1=NULL,*temp=NULL; int flag=0; //Tree is empty if(*bst==NULL) { printf("\nTree is empty!!!"); return; } //search for parent node and node to be deleted search(bst,&par,&del,&flag,n); //if node is not present if(flag==0) { printf("\n Data not found"); return; } //if node found //if left and right subtree of the concerned node is not empty if(del->left!=NULL && del->right!=NULL) { //find inorder successor del1=del->right; while(del1->left!=NULL) { par1=del1; del1=del1->left; } par1->left=del1->right;//set left link of parent of inorder successor to child of successor del1->left=del->left;//set left link of successor to the left descendant of to be deleted node del1->right=del->right;//set right link of successor to the right descendant of to be deleted node //delete the concerned node if(par->data>del->data) par->left=del1; else par->right=del1; free(del); return; } if(del->left==NULL && del->right==NULL) { if(del->data>par->data) par->right=NULL; else par->left=NULL; free(del); return; } if(del->right!=NULL) { if(del->data>par->data) par->right=del->right; else par->left=del->right; free(del); return; } if(del->left!=NULL) { if(del->data>par->data) par->right=del->left; else par->left=del->left; free(del); return; } } //traverse the tree in inorder void inorder(node*bt) { if(bt!=NULL) { inorder(bt->left); printf("%d\t",bt->data); inorder(bt->right); } } //traverse the tree in preorder void preorder(node*bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->left); preorder(bt->right); } } //traverse the tree in postorder void postorder(node*bt) { if(bt!=NULL) { postorder(bt->left); postorder(bt->right); printf("%d\t",bt->data); } } void main() { node*bst=NULL; insert(&bst,6); insert(&bst,2); insert(&bst,1); insert(&bst,5); insert(&bst,3); insert(&bst,4); insert(&bst,9); insert(&bst,7); insert(&bst,10); inorder(bst); printf("\n"); preorder(bst); delete(&bst,2); printf("\n"); postorder(bst); }