C++ exercises and solutions: OOP Binary Search Tree


Exercise

In this exercise, you will use the object-oriented programming in C++ to create a binary search tree data structure. The user that uses the binary search tree data structure will be able to add a new node to the tree, delete a node from the tree, traverse the tree, find the max and min nodes of three, and search for a node of the tree. The program should display a menu of choices to operate the Binary Search Tree data structure. See the sample menu below:

======================================================================

Binary Search Tree Operations Menu

=======================================================================

1. Add items

2. Delete items

3. View all items

4. Show max item

5. Show min item

6. Find an item

7. Exit

Binary Search Tree example

Binary Search Tree

 

Solution:

Building a binary search tree using Object-Oriented programming can takes multiples steps as this data structure is created by using structure.

Step 1: Defining the binary search tree node

In the code fragment below, the Node class represents a template for a node of the binary search tree. This Node class has three members. The data member is declared with the Type template. By using the template to define a time, you can have a flexible binary search tree. The users can specify their own data type that they like. The two members are pLeft and pRight. The pLeft pointer points to the left sub-tree, while the pRight points to the right sub-tree.


template <class Type> class BSTree;
template <class Type>


class Node {

public:
Node (const Type elem){pLeft=pRight=NULL; data=elem;}
public:
Type data; // the element data
Node<Type> *pLeft; // pLeft link
Node<Type> *pRight; // pRight link
};

For the next steps of our solution, please see their links on the menu at the left side of the page. 




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.