Binary Search Tree Implementation In C++

Im going to show you the implementation of Binary Search Tree In C++ to continue our Data Structure course in C++ language

You will find the code splitted to three parts at the first part Binary.h we are going to define function's header and at the second part Binary.cpp we are going to implement this function and in the last part main.cpp we are going call this function

Binary.h

  1 typedef int Entry;
  2  
  3 typedef struct node 
  4 { 
  5     Entry info; 
  6     struct node *right; 
  7     struct node *left; 
  8 }Nodetype; 
  9  
 10 typedef Nodetype *TreeNode; 
 11  
 12 void CreateTree (TreeNode *); 
 13 int EmptyTree (TreeNode ); 
 14 int FullTree (TreeNode ); 
 15 void InsertNode(TreeNode *,Entry *); 
 16 void InorderRec(TreeNode *, void(*pvisit)(Entry)); 
 17 void PreorderRec(TreeNode *, void(*pvisit)(Entry)); 
 18 void PostorderRec(TreeNode *, void(*pvisit)(Entry)); 
 19 int SearchValueRec(TreeNode *,Entry *,int); 
 20 void PrintPosistive(TreeNode *, void(*pvisit)(Entry)); 
 21 void Increament(TreeNode *); 
 22 int TreeSize(TreeNode *); 
 23 int TreeDepth(TreeNode *); 
 24 void PrintEven(TreeNode *, void(*pvisit)(Entry)); 
 25 void PrintOdd(TreeNode *, void(*pvisit)(Entry));

Binary.Cpp

  1 #include "Binary.h" 
  2 #include <stddef.h> 
  3 #include <stdio.h> 
  4 #include <stdlib.h> 
  5  
  6 void CreateTree (TreeNode *pt) 
  7 { 
  8     *pt=NULL; 
  9 } 
 10  
 11 int EmptyTree (TreeNode t) 
 12 { 
 13     return (!t); 
 14 } 
 15  
 16 int FullTree (TreeNode t) 
 17 { 
 18     return 0;
 19 } 
 20  
 21 void InsertNode(TreeNode *pt,Entry *item) 
 22 { 
 23     Nodetype *temp; 
 24     Nodetype *target; 
 25     Nodetype *p=(Nodetype *)malloc(sizeof(Nodetype)); 
 26     p->info=*item; 
 27     p->left=NULL; 
 28     p->right=NULL; 
 29     if(!*pt) 
 30     *pt=p; 
 31     else 
 32     { 
 33         temp=*pt; 
 34         while(temp) 
 35         { 
 36             target=temp; 
 37             if(*item < temp->info) 
 38                 temp=temp->left; 
 39             else 
 40                 temp=temp->right; 
 41         } 
 42         if(*item < target->info) 
 43             target->left=p; 
 44         else 
 45             target->right=p; 
 46     } 
 47 } 
 48 void InorderRec(TreeNode *pt, void(*pvisit)(Entry)){ 
 49     if (*pt)//if its not null 
 50     { 
 51     InorderRec(&(*pt)->left,pvisit); 
 52     (*pvisit)((*pt)->info); 
 53     InorderRec(&(*pt)->right, pvisit); 
 54     } 
 55 } 
 56 void PreorderRec(TreeNode *pt, void(*pvisit)(Entry)) 
 57 { 
 58     if(*pt)//if its not null 
 59     { 
 60         (*pvisit)((*pt)->info); 
 61         PreorderRec(&(*pt)->left,pvisit); 
 62         PreorderRec(&(*pt)->right,pvisit); 
 63     } 
 64 } 
 65 void PostorderRec(TreeNode *pt, void(*pvisit)(Entry)) 
 66 { 
 67     if(*pt)//if its not null 
 68     { 
 69         PostorderRec(&(*pt)->left,pvisit); 
 70         PostorderRec(&(*pt)->right,pvisit); 
 71         (*pvisit)((*pt)->info); 
 72     } 
 73 } 
 74 int SearchValueRec(TreeNode *pt,Entry *item ,int key) 
 75 { 
 76     if(!*pt)//if its null 
 77     return 0;
 78     if((*pt)->info==key) 
 79     { 
 80         *item=(*pt)->info; 
 81     return 1;
 82     } 
 83     if(key<(*pt)->info) 
 84         return SearchValueRec(&(*pt)->left,item,key); 
 85     else 
 86         return SearchValueRec(&(*pt)->right,item,key); 
 87 } 
 88 void Increament(TreeNode *pt) 
 89 { 
 90     int x=1; 
 91     if(*pt) 
 92     { 
 93         (*pt)->info=(*pt)->info+x;
 94         Increament(&(*pt)->left);
 95         Increament(&(*pt)->right); 
 96     } 
 97  
 98 } 
 99 void PrintPosistive(TreeNode *pt, void(*pvisit)(Entry)) 
100 { 
101     if(*pt) 
102     { 
103  
104     if((*pt)->info > 0) 
105         { 
106      PrintPosistive(&(*pt)->left,pvisit); 
107     (*pvisit)((*pt)->info); 
108      PrintPosistive(&(*pt)->right, pvisit); 
109         } 
110     } 
111 } 
112 int TreeSize(TreeNode *pt) 
113 { 
114     if(! *pt) 
115         return 0;
116     else 
117         return(1+TreeSize(&(*pt)->left)+TreeSize(&(*pt)->right)); 
118 } 
119 int TreeDepth(TreeNode *pt) 
120 { 
121     if(!*pt) 
122         return 0;
123         int a=TreeDepth(&(*pt)->left); 
124         int b=TreeDepth(&(*pt)->right); 
125         return (a>b) ? 1+a : 1+b ;
126 } 
127 void PrintEven(TreeNode *pt, void(*pvisit)(Entry)) 
128 { 
129     if(*pt) 
130     { 
131         if((*pt)->info % 2 == 0) 
132         (*pvisit)((*pt)->info); 
133         PrintEven(&(*pt)->left,pvisit); 
134         PrintEven(&(*pt)->right,pvisit); 
135     } 
136 } 
137  
138 void PrintOdd(TreeNode *pt, void(*pvisit)(Entry)) 
139 { 
140     if(*pt) 
141     { 
142         if((*pt)->info % 2 == 1) 
143         (*pvisit)((*pt)->info); 
144         PrintOdd(&(*pt)->left,pvisit); 
145         PrintOdd(&(*pt)->right,pvisit); 
146     } 
147 } 
148

Main.Cpp

  1 #include "Binary.h" 
  2 #include <stdio.h> 
  3 #include <iostream> 
  4 void DisplayEle(Entry E) 
  5 { 
  6     printf("%d\n",E); 
  7 } 
  8 int main () 
  9 { 
 10     int ch,key; 
 11     Entry e; 
 12     int x; 
 13     TreeNode t; 
 14         printf("\n\n\n\tMAIN MENU"); 
 15         printf("\n\n\t01. You Must Initialize Tree .. Press 1 For The First Use Only"); 
 16         printf("\n\n\t02. Insert A New Node In Tree"); 
 17         printf("\n\n\t03. Print Values OF Tree InOrder Travers LVR"); 
 18         printf("\n\n\t04. Print Values OF Tree InOrder Travers VLR"); 
 19         printf("\n\n\t05. Print Values OF Tree InOrder Travers LRV"); 
 20         printf("\n\n\t06. Search For Specific Element In Tree"); 
 21         printf("\n\n\t07. Increament Element In Tree"); 
 22         printf("\n\n\t08. Print Positive Element In Tree"); 
 23         printf("\n\n\t09. Print Size Of Tree"); 
 24         printf("\n\n\t10. Print Depth Of Tree"); 
 25         printf("\n\n\t11. Print Even Numbers"); 
 26         printf("\n\n\t12. Print Odd Numbers"); 
 27         printf("\n\n\t13. EXIT\n\n"); 
 28         scanf("%d",&ch); 
 29         while(ch!=13){ 
 30          
 31             if(ch==1) 
 32             { 
 33                 CreateTree(&t); 
 34                 printf("\n\nTree Is Intialized Successfully\n"); 
 35             } 
 36             else if (ch==2) 
 37             { 
 38                 if(FullTree(t)) 
 39                     printf("Tree FULL ... !\n"); 
 40                 else { 
 41                 printf("Enter The Value item\n"); 
 42                 scanf("%d",&e); 
 43                 InsertNode(&t,&e); 
 44                      } 
 45             } 
 46             else if (ch==3) 
 47             { 
 48                 printf("\nValue InOrder LVR\n"); 
 49                 InorderRec(&t,&DisplayEle); 
 50             } 
 51             else if (ch==4) 
 52             { 
 53                 printf("\nValue PreOrder VLR\n"); 
 54                 PreorderRec(&t,&DisplayEle); 
 55             } 
 56             else if (ch==5) 
 57             { 
 58                 printf("\nValue PostOrder LRV\n"); 
 59                 PostorderRec(&t,&DisplayEle); 
 60             } 
 61             else if (ch==6) 
 62             { 
 63                 printf("\nEnter The Value Your Are Going To Search For It\n"); 
 64                 scanf("%d",&key); 
 65                 if(!SearchValueRec(&t,&e,key)) 
 66                   printf("Value Isn't Found\n"); 
 67                 else 
 68                 { 
 69                 printf("Value Found Successfully And Its Value : %d\n",key); 
 70                 } 
 71             } 
 72             else if (ch==7) 
 73             { 
 74                 printf("\nPositive Values Increamented\n"); 
 75                 Increament(&t); 
 76                 printf("\nChoose From 3 To 5 To Print\n"); 
 77             } 
 78             else if (ch==8) 
 79             { 
 80                 printf("\nPriniting Posistive Numbers Only\n"); 
 81                 PrintPosistive(&t,&DisplayEle); 
 82             } 
 83             else if (ch==9) 
 84             { 
 85                 x=TreeSize(&t); 
 86                 printf("Size Of Tree is %d\n",x); 
 87             } 
 88             else if (ch==10) 
 89             { 
 90                 x=TreeDepth(&t); 
 91                 printf("Depth Of Tree is %d\n",x); 
 92             } 
 93             else if (ch==11) 
 94             { 
 95                 printf("Traversing Even Numbers\n"); 
 96                 PrintEven(&t,&DisplayEle); 
 97             } 
 98             else if (ch==12) 
 99             { 
100                 printf("Traversing Odd Numbers\n"); 
101                 PrintOdd(&t,&DisplayEle); 
102             } 
103         printf("\n\n\n\tMAIN MENU"); 
104         printf("\n\n\t01. You Must Initialize Tree .. Press 1 For The First Use Only"); 
105         printf("\n\n\t02. Insert A New Node In Tree"); 
106         printf("\n\n\t03. Print Values OF Tree InOrder Travers LVR"); 
107         printf("\n\n\t04. Print Values OF Tree InOrder Travers VLR"); 
108         printf("\n\n\t05. Print Values OF Tree InOrder Travers LRV"); 
109         printf("\n\n\t06. Search For Specific Element In Tree"); 
110         printf("\n\n\t07. Increament Element In Tree"); 
111         printf("\n\n\t08. Print Positive Element In Tree"); 
112         printf("\n\n\t09. Print Size Of Tree"); 
113         printf("\n\n\t10. Print Depth Of Tree"); 
114         printf("\n\n\t11. Print Even Numbers"); 
115         printf("\n\n\t12. Print Odd Numbers"); 
116         printf("\n\n\t13. EXIT\n\n"); 
117         scanf("%d",&ch); 
118         } 
119         system("PAUSR"); 
120     return 0;
121 }