Binary Search Trees

Question

Hi there! I have a question with regards to the Binary Search Tree Implemetation in C++. Here is the question below

Implement a simple (non-templated) BST which stores integers. Provide the following operations: Insert, Remove, inOrder traversal, preOrder traversal, postOrder traversal.

Use recursive routines for dealing with the tree.

Processing a node simply involves printing out the contents of the node, which in this case is the integer being stored in the node.

Data should come from test files. The main program should open the data file and insert into the tree and demonstrate other tree operations.

The point of this exercise is to demonstrate that you understand the BST. There is no need to go overboard with it and put in operations not asked for.

I have only created the Header file so far. Could anyone please take a look and advise if I am heading in the right direction?

using namespace std;
#ifndef BSTNODE_H
#define BSTNODE_H
class BSTNode
{
    private:
    //Defines the 'node' structure
    struct tree_node 
    {
     tree_node *left;   // left subtree has smaller elements
     tree_node *right;  // right subtree has larger elements
     int m_data;
    };
    //root * r;
    public:
     //The Constructor
     BSTNode();
     //The Destructor
       ~BSTNode();
       //Inserts a value into a BST, public function
     void insert(const m_data & d);
     //Removes a value from a BST, public function
     void remove(const m_data & d);
     //isEmpty function, public function
     bool isEmpty();
     BSTNode getData();
     void inOrder(const m_data & d);
     void preOrder(const m_data & d);
     void postOrder(const m_data & d);
};
#endif

Next I have to create the BSTNode.cpp file. Appreciate your response via mail to [email protected] Thanks in advance.

Answer 1

You seem to have forgotten to typedef the type m_data that you're using in the various methods, and I don't understand why you want a separate tree_node struct (rather than using the class itself?) nor why getData should return BSTNode rather than int.

Answer 2

   //Inserts a value into a BST, public function
    void insert(const m_data & d);
    //Removes a value from a BST, public function
    void remove(const m_data & d);
    //isEmpty function, public function
    bool isEmpty();
    BSTNode getData();
    void inOrder(const m_data & d);
    void preOrder(const m_data & d);
    void postOrder(const m_data & d);

m_data is a member, not a type. You should be using int here. Also, since your node is tree_node, the outer class should probably be representing the tree as a whole (ie, BSTree not BSTNode).

Also 'using namespace std;' is evil in headers, as it forces it upon anything that includes the header with no way to opt out. If you're going to use it, I'd recommend keeping it to .cpp files.

Answer 3

Its a classic question on BSTs - any good book on Data structures would give you the entire code. The following page contains code examples for C++ http://cslibrary.stanford.edu/110/BinaryTrees.html.

Traversal functions should not be a part of the BST class itself, infact the BSTNode should expose left/right node pointers - and the calling application should invoke it in the particular way. Or use a call back function and provide the traversal code inside your class, this way, it would be much cleaner.

Answer 4

Couple things - as others have pointed out, you will have to use

void insert(const int & d);
//Removes a value from a BST, public function
void remove(const int & d);
//isEmpty function, public function
bool isEmpty();
BSTNode getData();
void inOrder(const int & d);
void preOrder(const int & d);
void postOrder(const int & d);

The other things is that you have commented out your root node. Although you defined it wrong, you will have to include a root node in the class. The correct definition would be

tree_node *root;

Also, as was pointed out before, remove the

using namespace std;

from the header file and put it into your implementation file instead.

That is all that I can see right now.

Answer 5

Another problem is that the class as specified declares a nested type, and methods, but no member data.

---

You can declare the traversal functionality using iterators: e.g. the preorder method returns an interator, which you can dereference to a node, or increment to point to the next node in the preorder sequence.

Or, you might declare traversal functionality using callbacks: i.e. the caller passes a callback instance to the preorder method, the preorder method traverses the tree and invokes the callback method for each node: the callback method would take a node (or, more specifically, node data) as a parameter, and might return a boolean that would let the callback spevify that it wants to abend the traversal.

Answer 6

I would add a search method too.

bool search(int whatIlookfor);

or even better

tree_node* search(int whatIlookfor);

Also, keep tree_node *root in a safe place.

Answer 7

Something trivial:

tree_node *left;   // left subtree has smaller elements

In general, left subtree also contains the equal elements.

Answer 8

• using left and right pointers of the struct type in your example, would restrict flexibilty - suppose I take your BST and traverse to left child of the root, and then want to call operations on this new subtree. I cannot since the pointers are of the struct type. I would rather suggest using both pointers as of type BSTNode.

  BSTNode *left;

  BSTNode *right;

  This would also solve your root problem (no explicit root pointer required), since the pointer you use to reference your object in main, will point to root anyway.

• The traversal functions should not require any arguments, when they would essentially traverse the whole tree and print all the data items along. The data item can be passed to another search member function for searching its position as pointed out already by TrueStar.

• I also suggest few private member functions to reduce complexity of your public member functions (DeleteNodeCaseB(int data) would call DeleteNodeCaseA(int data) from within time and again) -

  BSTNode * setleft(int data);

  BSTNode * setright(int data);

  void DeleteNodeCaseA(int data) /* either or both of left and right child does not exist */

  void DeleteNodeCaseB(int data) /* has both left and right child */

Answer 9

Since you're using C++, you may want to consider using some standard libraries instead of trying to implement it all yourself? STL libraries come with a red-black tree, which may suit your application better. Binary trees can get lop-sided or degenerate into a link-list.

PS: Of course, this assumes that you are not doing a homework assignment.

Answer 10

All operations on binary search trees were explained here.. http://www.cpp-programming.net/c-tidbits/binary-search-trees/