C++ tutorial: C++ code of binary search tree


C++ Structure: Building a Binary Search Tree

Step 8:Combine the C++ code together

This is the complete C++ code of the Binary Search Tree:

#include <;iostream.h> #include <conio.h>
using namespace std; struct ListElem{
int data; // the element data
ListElem *pLeft; // pLeft links to the left-sub tree
ListElem *pRight; // pRight link to the right sub-tree };

 //---------------------------------------------------------

ListElem *Root;

ListElem *Insert (ListElem **T,int Tar);

 ListElem *Delete(ListElem **T, int Tar);//delete item from the list

void getallval(ListElem *T);//print out all items on the screen

ListElem *find(ListElem *T,int Tar);

ListElem *findmin(ListElem *T); ListElem *findmax(ListElem *T);
ListElem *find(ListElem *T, int Tar){

 if(T==NULL) return NULL;

if(Tardata) //look in the left side
return find(T->pLeft,Tar); else if(Tar>T->data)//look in the right side

 return find(T->pRight,Tar); else return T; //found node }
//insert item ListElem *Insert (ListElem **T,int Tar) {
if(*T==NULL)

{ ListElem *item;//new element to be inserted item=(ListElem *)malloc(sizeof(Node)); //allocate space if(!item) {printf("Memory problem..."); exit(100);}

item->data=Tar; item->pLeft=NULL; item->pRight=NULL; *T=item;


} else { if(Tar<(*T)->data) (*T)->pLeft=Insert(&(*T)->pLeft, Tar); else if(Tar>(*T)->data) (*T)->pRight=Insert(&(*T)->pRight,Tar); } return *T; } //Print out all items on the screen void getallval(ListElem *T) { if(T!=NULL) {
cout<data<<"\t";
getallval(T->pLeft);
getallval(T->pRight);
}
}

//find min node

ListElem *findmin(ListElem *T){

if(T==NULL) return NULL; else if(T->pLeft==NULL) return T; else return findmin(T->pLeft); }

//find max node ListElem *findmax(ListElem *T){ if(T==NULL) return NULL; else if(T->pRight==NULL) return T; else return findmax(T->pRight); }
//Delete node ListElem *Delete(ListElem **T, int Tar){ ListElem *Min,*Temp; if((*T)==NULL) return NULL; else if(Tar<(*T)->data) {return Delete(&(*T)->pLeft,Tar); }

//look in the left else if(Tar>(*T)->data) return Delete(&(*T)->pRight, Tar);//look in the right else{ //found node to delete if((*T)->pLeft && (*T)->pRight) //two children { Min=findmin((*T)->pRight); (*T)->data=Min->data; (*T)->pRight=Delete(&(*T)->pRight,(*T)->data); }


else{


//one or zero child Temp=*T; if((*T)->pLeft==NULL) {(*T)=(*T)->pRight; } else if((*T)->pRight==NULL) {(*T)=(*T)->pLeft;} Temp=NULL; } return *T; } }
void showmenu(){ cout<<"=================================\n"; cout<<"Binary Search Tree Operations Menu\n"; cout<<"=================================\n"; cout<<"1.Add a new item\n"; cout<<"2.Delete an item\n"; cout<<"3.Show number of items\n"; cout<<"4.Show all items\n"; cout<<"5.Show min node\n"; cout<<"6.Exit\n";
} void select(){ int val, ch; char yes='y'; ListElem *Temp; while(yes=='y'){ cout<<"Enter your choice:";cin>>ch; switch(ch){ case 1: cout<<"Value:";cin>>val; Temp=Insert(&Root,val); break;
case 2: cout<<"Value to delete:";cin>>val; Temp=Delete(&Root,val); break;
case 3: cout<<"All items:\n"; getallval(Root); break;
case 4: Temp=findmin(Root); cout<data< case 5: Temp=findmax(Root); cout<data< case 6: cout<<"Value:";cin>>val; Temp=find(Root,val); cout<data; break;
case 7: exit(0);

default: cout<<"Invalid choice"; } cout<<"Continue?y/n:";cin>>yes; } Temp=NULL; } int main(){ showmenu(); select(); getch(); return 0; } //




Comments




This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.