Reputation:
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.
Upvotes: 2
Views: 2517
Reputation: 16814
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 */
Upvotes: 1
Reputation: 3156
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.
Upvotes: 1
Reputation: 13035
Something trivial:
tree_node *left; // left subtree has smaller elements
In general, left subtree also contains the equal elements.
Upvotes: 2
Reputation:
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.
Upvotes: 1
Reputation: 56123
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.
Upvotes: 1
Reputation: 12205
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.
Upvotes: 1
Reputation: 2406
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.
Upvotes: 1
Reputation: 231451
//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.
Upvotes: 3
Reputation: 882751
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
.
Upvotes: 3