Hey Daniweb, I'm back again!
This time around, my assignment is to implement a binary tree, a tree node, and a binary search tree using the class definitions given to us by our teacher. Implementing the TreeNode was no trouble at all, but when I started on the Tree itself, that is when things started to get...confusing.
I tried asking the teacher some questions, and he told me that the Tree constructor that takes a value and two trees, left and right, is supposed to set the trees as the left and right subtree of the tree that is being constructed.
The other question I asked was about the recursion in the traversal methods. He said, "For each one, you just need to add a helper function with a pointer as its parameter." I don't know if he meant that we are supposed to create a method that points to the left/right child of the node that is the parameter, or something else.
I tried to scour my book for the class, "Data Structures and Algorithm Analysis in C++" and google in search of examples to point me in the right direction, but all the examples that I've seen of recursive traversals and the like have been methods that have a node pointer or such as a parameter. I'm probably missing something really obvious.
I've done some floundering around on my own, trying to figure it out, but I feel like I've just gone in circles. I'll post what I have.
Line 12 triggers a linker error, and nothing my teacher has told me indicates that the code is wrong. When he said left/right subtree, did he mean to set the left/right values of the root node to the "roots" of these two trees? I still don't understand why he would pass two trees, and by value, to this Tree constructor. Wouldn't a TreeNode pointer suffice? I get the nagging feeling that I'm missing something obvious, and I was hoping someone could point it out to me, since it has evaded me for 7 hours today :/
template <class Comparable>
class TreeNode {
public: Comparable item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
TreeNode (Comparable value) ; // Constructor. Make a node containing value.
TreeNode (Comparable value, TreeNode *leftTree, TreeNode *rightTree) ; // Constructor.
};
// Constructor. Make a node containing value.
template <class Comparable>
TreeNode<Comparable>::TreeNode (Comparable value)
{
item = value;
left = NULL;
right = NULL;
}
// Constructor. Make a node containing value
//and set the left and right pointers to the passed params
template <class Comparable>
TreeNode<Comparable>::TreeNode (Comparable value, TreeNode *leftTree, TreeNode *rightTree)
{
item = value;
left = leftTree;
right = rightTree;
}#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#include "TreeNode.h"
template <class Comparable>
class Tree
{
public :
TreeNode <Comparable> *root; //pointer to root node
//pointer to left subtree
//leftSubTree was created by me as a guess solution to my teacher's answer
//im not even sure if we are allowed to add members to this class
Tree <Comparable> *leftSubTree;
//pointer to right subtree, same as leftSubTree
Tree <Comparable> *rightSubTree;
Tree () {root = NULL;} // default constructor
Tree (Comparable value) ; // constructor ;create a single node tree
Tree(Comparable value , Tree left, Tree right); // constructor
Tree (Tree &other); // copy constructor
Tree(TreeNode <Comparable> *r); // constructor taking a pointer to a tree node
Tree & operator = (const Tree &rhs); // overload assignment operator
~Tree() {delete root;} // destructor
//like with leftSubTree, I created the following three these, though I am
//unsure if we are allowed to add additional methods to the class
//helper method to return the left child of the node passed
TreeNode <Comparable> *leftChild (TreeNode <Comparable> *currentNode) {return currentNode->left;}
//helper method to return the right child of the node passed
TreeNode <Comparable> *rightChild (TreeNode <Comparable> *currentNode) {return currentNode->right;}
//helper method to clear out the tree
void makeEmpty(TreeNode <Comparable> * & t);
// the following recursive functions that print the tree node
void preorder ();
void postorder ();
void inorder ();
// the following recursive functions that print the tree node and its level #
void preorder (int level);
void postorder (int level);
void inorder (int level);
// the following recursive function prints the tree node with its parent and level number
void preorder(TreeNode <Comparable> *p , int level); // recursive preorder with level #
void postorder(TreeNode <Comparable> *p , int level); // recursive postorder with level #
void inorder(TreeNode <Comparable> *p , int level); // recursive inorder with level #
void byLevel(); // print the tree by level , use of STL queue class
int weight() ; // returns the total number of nodes in the tree
int height(); // returns the height of the tree
// the following three are non-recursive version use of STL stack class
void pre() ; // non-recursive preorder
void in() ; // non-recursive inorder()
void post() ; // non-recursive postorder()
};
// constructor ;create a single node tree
template <class Comparable>
Tree<Comparable>::Tree (Comparable value)
{
root = new TreeNode<Comparable> (value, NULL, NULL);
}
// constructor ;create a single node tree
template <class Comparable>
Tree<Comparable>::Tree (TreeNode <Comparable> *r)
{
root = new TreeNode<Comparable> (r->item, r->left, r->right);
}
// constructor with up to 3 nodes: a root and two children
template <class Comparable>
Tree<Comparable>::Tree (Comparable value, Tree left, Tree right)
{
root = new TreeNode<Comparable> (value);
leftSubTree = &left;
rightSubTree = &right;
}
// overload assignment operator
template <class Comparable>
Tree <Comparable> &Tree<Comparable>::operator = (const Tree &rhs)
{
if (this != &rhs)
{
//makeEmpty(); //havent written these methods yet
//root = clone(rhs.root);
}
return *this;
}
// helper function that returns the height of the tree
template <class Comparable>
int Tree<Comparable>::height ()
{
if (root == NULL)
return 0; //tree is empty
}
// recursive traversal - preorder
template <class Comparable>
void Tree<Comparable>::preorder()
{
//had no idea how to start this, given that it has no parameter
}
//non-recursive traversal - preorder
template <class Comparable>
void Tree<Comparable>::pre()
{
if (root == NULL)
return; //empty tree
TreeNode <Comparable>* cur = root;
stack<TreeNode<Comparable>*> stk;
stk.push(cur);
while(!stack.empty())
{
cur = stk.top();
stk.pop();
while (cur != NULL)
{
cout << cur->item << " ";
if (cur->right != NULL)
stk.push(cur->right);
cur = cur->left;
}
}
cout << "\n\n End of non-recursive preorder print \n";
}
//non-recursive traversal - inorder
template <class Comparable>
void Tree<Comparable>::in()
{
if (root == NULL)
return; //empty tree
TreeNode <Comparable>* cur = root;
stack<TreeNode<Comparable>*> stk;
stk.push(cur);
while (cur->left != NULL)
{
cur = cur->left;
stk.push(cur);
}
while(!stack.empty())
{
cur = stk.top();
cout << cur->item << " ";
stk.pop();
if (cur->right != NULL)
{
cur = cur->right;
stk.push(cur);
while (cur->left != NULL)
{
cur = cur->left;
stk.push(cur);
}
}
}
cout << "\n\n End of non-recursive inorder print \n";
}
//recursive make empty method
template <class Comparable>
void Tree<Comparable>::makeEmpty(TreeNode <Comparable> * & t)
{
//code not yet written :)
}template < class Comparable>
class bst : public Tree< Comparable> {
public : bst(): Tree() {} ;
bst(Comparable item):Tree(item) {};
void insert(Comparable item) ;
TreeNode *find(Comparable item) ;
TreeNode *remove(Comparable item ) ;
} ;#include <stdio.h>
#include <iostream>
using namespace std;
#include "Tree.h"
int main()
{
Tree <int> test(5);
Tree <int> test2(10);
Tree <int> test3(20);
Tree <int> test4(50, test2, test3);
cout << test.root->item;
return 0;
}