Program Plan This Program defines Binary Search Tree Class which allows duplicates number entry A class has member functions to perform the following operations: Input numbers for Binary Tree to allow duplicates Display the Numerical Binary Tree Delete elements from Binary Tree Program Description This Program defines Binary Search Tree Class which allows duplicates number entry. In general, a BST follows the rule of left < root <= right, which needs to be overridden in this program which adds complexity in searching the elements from BST. We are allowing duplicate entry only at different levels of the tree. Program: /* * C++ Program To Implement Binary Search Tree for Numbers * This Program Allows duplicates in BST */ #include<iostream> #include<cstdlib> usingnamespace std; /* * Node Declaration */ struct node { int info; struct node *left; struct node *right; }*root; /* * Class Declaration */ class BST { public: voidfind(int, node &, node **); voidinsert(node *, node *); void del(int); voidcase_a(node *,node *); voidcase_b(node *,node *); voidcase_c(node *,node *); voidpreorder(node *); voidinorder(node *); voidpostorder(node *); voiddisplay(node *,int); BST() { root =NULL; } }; /* * Main Contains Menu */ intmain() { int choice,num; BST bst; node *temp; while(1) { cout<<"-----------------"<<endl; cout<<"Operations on BST"<<endl; cout<<"-----------------"<<endl; cout<<"1.Insert Element "<<endl; cout<<"2.Delete Element "<<endl; cout<<"3.Inorder Traversal"<<endl; cout<<"4.Preorder Traversal"<<endl; cout<<"5.Postorder Traversal"<<endl; cout<<"6.Display"<<endl; cout<<"7.Quit"<<endl; cout<<"Enter your choice : "; cin>>choice; switch(choice) { case1: temp =new node; cout<<"Enter the number to be inserted : "; cin>>temp->info; bst.insert(root, temp); break; case2: if(root ==NULL) { cout<<"Tree is empty, nothing to delete"<<endl; continue; } cout<<"Enter the number to be deleted : "; cin>>num; bst.del(num); break; case3: cout<<"Inorder Traversal of BST:"<<endl; bst.inorder(root); cout<<endl; break; case4: cout<<"Preorder Traversal of BST:"<<endl; bst.preorder(root); cout<<endl; break; case5: cout<<"Postorder Traversal of BST:"<<endl; bst.postorder(root); cout<<endl; break; case6: cout<<"Display BST:"<<endl; bst.display(root,1); cout<<endl; break; case7: exit(1); default: cout<<"Wrong choice"<<endl; } } } /* * Find Element in the Tree */ voidBST::find(int item, node &par, node **loc) { node *ptr,*ptrsave; if(root ==NULL) { *loc=NULL; *par =NULL; return; } if(item == root->info) { *loc= root; *par =NULL; return; } if(item < root->info) ptr= root->left; else ptr= root->right; ptrsave= root; while(ptr!=NULL) { if(item ==ptr->info) { *loc=ptr; *par =ptrsave; return; } ptrsave=ptr; if(item <ptr->info) ptr=ptr->left; else ptr=ptr->right; } *loc=NULL; *par =ptrsave; } /* * Inserting Element into the Tree */ voidBST::insert(node *tree, node *newnode) { if(root ==NULL) { root =newnode; root->info =newnode->info; root->left =NULL; root->right =NULL; cout<<"Root Node is Added"<<endl; return; } // if (tree->info == newnode->info) // { // cout<<"Element already in the tree"<<endl; // return; // } if(tree->info>newnode->info) { if(tree->left !=NULL) { insert(tree->left,newnode); } else { tree->left =newnode; (tree->left)->left =NULL; (tree->left)->right =NULL; cout<<"Node Added To Left"<<endl; return; } } else { if(tree->right !=NULL) { insert(tree->right,newnode); } else { tree->right =newnode; (tree->right)->left =NULL; (tree->right)->right =NULL; cout<<"Node Added To Right"<<endl; return; } } } /* * Delete Element from the tree */ voidBST::del(int item) { node *parent,*location; if(root ==NULL) { cout<<"Tree empty"<<endl; return; } find(item,&parent,&location); if(location ==NULL) { cout<<"Item not present in tree"<<endl; return; } if(location->left ==NULL&& location->right ==NULL) case_a(parent, location); if(location->left !=NULL&& location->right ==NULL) case_b(parent, location); if(location->left ==NULL&& location->right !=NULL) case_b(parent, location); if(location->left !=NULL&& location->right !=NULL) case_c(parent, location); free(location); } /* * Case A */ voidBST::case_a(node *par, node *loc) { if(par ==NULL) { root =NULL; } else { if(loc== par->left) par->left =NULL; else par->right =NULL; } } /* * Case B */ voidBST::case_b(node *par, node *loc) { node *child; if(loc->left !=NULL) child =loc->left; else child =loc->right; if(par ==NULL) { root = child; } else { if(loc== par->left) par->left = child; else par->right = child; } } /* * Case C */ voidBST::case_c(node *par, node *loc) { node *ptr,*ptrsave,*suc,*parsuc; ptrsave=loc; ptr=loc->right; while(ptr->left !=NULL) { ptrsave=ptr; ptr=ptr->left; } suc=ptr; parsuc=ptrsave; if(suc->left ==NULL&&suc->right ==NULL) case_a(parsuc,suc); else case_b(parsuc,suc); if(par ==NULL) { root =suc; } else { if(loc== par->left) par->left =suc; else par->right =suc; } suc->left =loc->left; suc->right =loc->right; } /* * Pre Order Traversal */ voidBST::preorder(node *ptr) { if(root ==NULL) { cout<<"Tree is empty"<<endl; return; } if(ptr!=NULL) { cout<<ptr->info<<" "; preorder(ptr->left); preorder(ptr->right); } } /* * In Order Traversal */ voidBST::inorder(node *ptr) { if(root ==NULL) { cout<<"Tree is empty"<<endl; return; } if(ptr!=NULL) { inorder(ptr->left); cout<<ptr->info<<" "; inorder(ptr->right); } } /* * Postorder Traversal */ voidBST::postorder(node *ptr) { if(root ==NULL) { cout<<"Tree is empty"<<endl; return; } if(ptr!=NULL) { postorder(ptr->left); postorder(ptr->right); cout<<ptr->info<<" "; } } /* * Display Tree Structure */ voidBST::display(node *ptr,int level) { inti; if(ptr!=NULL) { display(ptr->right, level+1); cout<<endl; if(ptr== root) cout<<"Root->: "; else { for(i=0;i<level;i++) cout<<" "; } cout<<ptr->info; display(ptr->left, level+1); } } Sample Output ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 9 Root Node is Added ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 4 Preorder Traversal of BST: 9 ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 5 Node Added To Left ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 12 Node Added To Right ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 8 Node Added To Right ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 5 Node Added To Left ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 1 Enter the number to be inserted: 13 Node Added To Right ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 6 Display BST: 13 12 Root->: 9 8 5 5 ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 2 Enter the number to be deleted: 5 ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice: 6 Display BST: 13 12 Root->: 9 8 5 ----------------- Operations on BST ----------------- 1. Insert Element 2. Delete Element 3. Inorder Traversal 4. Preorder Traversal 5. Postorder Traversal 6. Display 7. Quit Enter your choice:

C++ How to Program (Early Objects Version)

10th Edition

ISBN: 9780134448824

Author: Paul Deitel; Harvey M. Deitel

Publisher: Pearson Education (US)

See similar textbooks

Concept explainers

Declaring and Defining the function

A set of statements, which performs a particular task is called a function. The program gains modularity by using function. The application is quite easy to understand, read, and edit when they are created with functions. The developer/programmer creates…

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 19, Problem 19.15E

Chapter 19, Problem 19.17E

Students have asked these similar questions

4. |z + 5 - 5i| = 7

14. dz, C: |z❘ C: |z❘ = 0.6 ze² - 2iz H

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Solution Summary: The author explains that the program defines a Binary Search Tree Class which allows duplicates number entry.

Concept explainers

Want to see the full answer?

Chapter 19 Solutions