# Binary tree Implementation on C Algorithm and Source Code

Binary tree Implementation on C++ – Algorithm and Source Code

Algorithm for inserting a node in a binary tree:

`1. Declare and initialize necessary variables2. Read the data item to be inserted in the tree say x.3. Create a new node with its left and right pointers to null.4. Assign data x to info field of new node.5. If (tree == NULL)       then tree = address of new node    else if (x < tree -> info)       if(tree->left == NULL)          then tree->left = new node       else          tree = tree->left    repeat step 5.    else if(x>tree->info)       if(tree->right == NULL)          then tree->right = new node       else          tree = tree->right     repeat step 5     else if(x == tree->info)          print "Duplicated data" and exit6. For next insertion, goto step 5.`

Deletion Algorithm

`1. Declare and initialize necessary variable2. Read data to be deleted say x.3. Find th enode where data is exist.    if node is not found       print "node not found" and exit4. If the node has no subtree       * then assign the father node's pointer with null that points to the node       * delete the node that contains data item.5. If the node has to be deleted has only one subtree        * move its son up, to take its place       * delete the node that contains data item6. If the node has to be deleted has two subtrees       * set the information of node to be deleted by the information of leftmost node of rightmost subtree of the node to be deleted7. For next deletion, goto step 2`

Source Code for Insertion , Deletion, inorder, preorder and postorder tree traversal

```#include
#include

using namespace std;
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class Binary_tree{
public:
Binary_tree();
void insert1(int);
tree *insert2(tree *, tree *);
void Delete(int);
void pretrav(tree *);
void intrav(tree *);
void posttrav(tree *);
};

Binary_tree::Binary_tree(){
root = NULL;

}

tree* Binary_tree::insert2(tree *temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info < newnode->info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}

void Binary_tree::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}

void Binary_tree::pretrav(tree *t = root){
if(root == NULL){
cout<<"Nothing to display";
}else
if(t != NULL){
cout<info<<" ";
pretrav(t->Left);
pretrav(t->Right);
}
}

void Binary_tree::intrav(tree *t = root){
if(root==NULL){
cout<<"Nothing to display";
}else
if(t!=NULL){
intrav(t->Left);
cout<info<<" ";
intrav(t->Right);
}
}

void Binary_tree::posttrav(tree *t = root){
if(root==NULL){
cout<<"Nothing to display";
}else
if(t!=NULL){
posttrav(t->Left);
posttrav(t->Right);
cout<info<<" ";
}
}

void Binary_tree::Delete(int key)
{
tree *temp = root,*parent = root, *marker;
if(temp==NULL)
cout<<"The tree is empty"<
else{
while(temp!=NULL && temp->info!=key){
parent=temp;
if(temp->info
temp=temp->Right;
}else{
temp=temp->Left;
}
}
}
marker=temp;
if(temp==NULL)
cout<<"No node present";
else if(temp==root){
if(temp->Right==NULL && temp->Left==NULL){
root=NULL;
}
else if(temp->Left==NULL){
root=temp->Right;
}
else if(temp->Right==NULL){
root=temp->Left;
}
else{
tree *temp1;
temp1 = temp->Right;
while(temp1->Left!=NULL){
temp=temp1;
temp1=temp1->Left;
}
if(temp1!=temp->Right){
temp->Left=temp1->Right;
temp1->Right=root->Right;
}
temp1->Left=root->Left;
root=temp1;
}
}
else{
if(temp->Right==NULL && temp->Left==NULL){
if(parent->Right==temp)
parent->Right=NULL;
else
parent->Left=NULL;
}
else if(temp->Left==NULL){
if(parent->Right==temp)
parent->Right=temp->Right;
else
parent->Left=temp->Right;
}
else if(temp->Right==NULL){
if(parent->Right==temp)
parent->Right=temp->Left;
else
parent->Left=temp->Left;
}else{
tree *temp1;
parent=temp;
temp1=temp->Right;
while(temp1->Left!=NULL){
parent=temp1;
temp1=temp1->Left;
}
if(temp1!=temp->Right){
temp->Left=temp1->Right;
temp1->Right=parent->Right;
}
temp1->Left=parent->Left;
parent=temp1;
}
}
delete marker;
}

int main(){
Binary_tree bt;
int choice, n, key;
while(1){
cout<<"\n\t1. Insert\n\t2. Delete\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit"<
cin>>choice;

switch(choice){
case 1:
cout<<"Enter item: ";
cin>>n;
bt.insert1(n);
break;
case 2:
cout<<"Enter element to delete: ";
cin>>key;
bt.Delete(key);
break;
case 3:
cout<
bt.pretrav();
break;
case 4:
cout<
bt.intrav();
break;
case 5:
cout<
bt.posttrav();
break;
case 6:
exit(0);
}
}
return 0;
}

Related PostsDecember 27, 2012 Breadth First Search in C++ – Algorithm and Source CodeDecember 28, 2012 Depth First Search in C++ – Algorithm and Source CodeSeptember 19, 2012 Analysis of Tower of Hanoi Problem with Algorithm and Source code in CCSeptember 22, 2012 Binary Tree and Operations on Binary TreeNovember 5, 2012 Implementation of Dijkstras Shortest Path Algorithm in CZemanta

```