I am going out of town and don't have access to my professor and / or tutors for the weekend, and we have an assignment involving a BST. I have done all of my insert, remove, and search functions, and went to the tutor about the remaining ones I have, but he is a genius and I don't necessarily "follow" all he is saying all the time.
Anyways, I need help with 3 functions, some of which I have actual code for, others the pseudo-code, which I need further assistance on (not asking for code here, just ideas/clarification).
Here is the class implementation provided:
//bst.h typedef int T; class BST {
public: BST(); //constructor
~BST(); //destructor bool empty();
bool search(const T& item);
void insert(const T& item);
void remove(const T& item);
int level(const T& item);
void leveltraversal(ostream& out);
void nonrecurs_preorder(ostream& out);
int height();
private: class BinNode {
public: T data;
// non-recursive
BinNode* left; BinNode* right; BinNode() : left(0), right(0) {} BinNode(T item): data(item), left(0), right(0) {}
}; typedef BinNode* BinNodePtr; BinNodePtr myRoot;
};And now for my questions:
1.)
int level(const T& item);- Write a function member level() which determines the level of an given item in the tree. The root of the BST is at level 0, and its children are at level 1, and so on.
-- I have a general idea of this, which would be just do do a typical search of the item passed into the function, but add a counter that increments every time we go to a right or a left subtree.
2)
int height();-Write a member function height() to return the height of a tree
--This is probably my most problematic function, I got help from the tutor, and we worked a little something out. I know that I need to do this recursively via a helper function:
int privateHeight(BinNodePtr subRoot);--Within this function I know that I need to initialize some height variable to 1, and then break into a loop:
int height = 1;
if(subRoot!=0){
//this is where i fall apart
//I know I need to call the privateHeight() function recursively and compare
//which of the two sides is larger, in case it is an unbalanced tree, but I dont have the slightest idea
//on how I would do this :(
return 1 + privateHeight(the larger side);
}//end if
else return 0
}3. Sorry this is so long, but here is my last one:
void levelTraversal(ostream& out);-Write a member function leveltraversal() to traverse a tree level by level; that is, first visit the root, then all nodes on level 1 (children of the root), then all nodes on level 2, and so on. Nodes on the same level should be visited in order from left to right.
--This one is more to verify that I am on the right track, my code compiles fine, but the passing of ostream& out is throwing me off in my client program when I go to test this, does it need to be done differently with another helper function? I didn't think so since we are using the STL queue, or maybe I am just having an issue with my main.cpp
void BST::leveltraversal(ostream& out){
queue<BST::BinNodePtr> myQ;
if (myRoot == NULL)
return;
BinNodePtr p = myRoot;
myQ.push(p);
while(!myQ.empty()){
cout << myQ.front();
p = myQ.front()->left;
myQ.push(p);
p = myQ.front()->right;
myQ.push(p);
cout << myQ.front();
myQ.pop();
}
}Thanks for your help, sorry for the length of the post