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;
}

Look at it in our eyes. You talk a little and dump a whole *lot of code on
us. Make it simpler for us to help you by shows only the relevant code
and stating the problem correctly.

I have a hunch, that you are not getting the theory behind a binary
search tree. You should re-read your text book more carefully.
TreeNode *left, and TreeNode* right, both are subtrees. Sure
it is a node, but if you draw a picture, you will soon realize and see
that it is also a subtree. That is why trees are recursive in nature.

As for your problem, I am not sure what to do, since your problem
wasn't stated clearly.


-------------------------------------------------------------------------------------------
*lot is subjective of course

Sorry. I guess what was confusing me about the constructor was that it was being passed two trees instead of two nodes. Is the constructor supposed to receive two trees, or two nodes instead? If it is supposed to be two trees, am I supposed to set the root.left and root.right to the roots of the left and right trees being passed?

And for the recursion, how am I supposed to do a recursive traversal using a method that doesn't have a node pointer as a parameter? All the examples of recursive tree traversals that I have been able to find have a node pointer as a parameter.

Edited 6 Years Ago by HoldmysunnyD: n/a

Here is the code I am not sure what you mean.
my_bst_node.h

//create bst node

#ifndef MY_BST_NODE_H
#define MY_BST_NODE_H

#include <iostream>

using namespace std;

template<class KT,class DT>
class my_bst_node
{
public:
	my_bst_node();
	my_bst_node(KT tag, DT info, my_bst_node* l=0, my_bst_node* r=0);

	KT key;
	DT data;
	my_bst_node* left;
	my_bst_node* right;
};

template<class KT, class DT>
my_bst_node<KT,DT>::my_bst_node()
{
		left=right=0;
}

template<class KT, class DT>
my_bst_node<KT,DT>::my_bst_node(KT tag, DT info, my_bst_node* l, my_bst_node* r)
{
		key=tag;
		data=info;
		left=l; 
		right=r;
}

#endif

my_bst.h

//operations that a bst can perform

#ifndef MY_BST_H
#define MY_BST_H
#include <iostream>
#include "my_bst_node.h"

using  namespace std;

template<class KT,class DT>
class my_bst
{
public:
	//default constructor
	my_bst();

	//inserts a new node into binary tree
	void insert(KT searchkey, const DT &newDataItem);

	//search for the key and if found return true
	void search(KT searchkey);

	//prints out tree based on visiting the root node, then the left subtree and last the right subtree
	void preorder_print();

	//prints out tree based on visiting the left subtree, then the root node, and last the right subtree
	void inorder_print();

	//prints out tree based on visiting the left subtree, then the right subtree, and last the root node
	void postorder_print();

	//remove data item
	void remove(KT searchkey);

	//returns height of BST
	int height();

	//check if tree is balanced
	void balanced();

	//output tree structure
	void show(int tree);

private:
	my_bst_node<KT,DT>* root;

	//helper function of insert
	void insert(my_bst_node<KT,DT>*& newnode ,my_bst_node<KT,DT>*& nodepointer);

	//helper function of search
	void search(my_bst_node<KT,DT>*& d, const KT& searchkey);

	//helper function of preorder print
	void preorder_print(my_bst_node<KT,DT>*& f);

	//helper function of inorder print
	void inorder_print(my_bst_node<KT,DT>*& g);

	//helper function of postorder print
	void postorder_print(my_bst_node<KT,DT>*& n);

	//helper function of remove
	void remov(my_bst_node<KT,DT>*& n, KT deletekey);

	//function to delete the node
	void deletenode(my_bst_node<KT,DT>*& g);

	//function to find the maximum value
	my_bst_node<KT,DT>* findmax(my_bst_node<KT,DT>* h);

	//helper function of get height
	int height(my_bst_node<KT,DT>* p);

	//helper function of balanced
	bool balanced(my_bst_node<KT,DT>*& j);

	//helper function of show
	void printLevelOrder(my_bst_node<KT,DT>* t, int height);

	//helper function of show
	void printLevelOrderAux(my_bst_node<KT,DT>* t, int level);
};

template <class KT, class DT>
my_bst<KT,DT>::my_bst()
{
	root=NULL;
}

template <class KT, class DT>
void my_bst<KT,DT>::insert(KT searchkey, const DT& newDataItem)
{
	my_bst_node<KT,DT>* temp=new my_bst_node<KT,DT>(searchkey, newDataItem);
	insert(temp, root);
}
	
template <class KT, class DT>
void my_bst<KT,DT>::insert(my_bst_node<KT,DT>*&	newnode ,my_bst_node<KT,DT>*& nodepointer)
{
   //if empty tree
   if(nodepointer==NULL)
   {
		nodepointer=newnode;
   }
   //key less than root nodes 
   else if((newnode->key)<=(nodepointer->key))
   {
	   insert(newnode,nodepointer->left);
   }
   //key greater than root nodes
   else
   {
	   insert(newnode,nodepointer->right);
   }
}

template <class KT, class DT>
void my_bst<KT,DT>::search(KT searchkey)
{
	my_bst_node<KT,DT>* temp=root;
	search(temp,searchkey);
}

template <class KT, class DT>
void my_bst<KT,DT>::search(my_bst_node<KT,DT>*&d ,const KT& searchkey)
{
	//if empty tree
	if(d==NULL)
	{
		cout<<"false\n";
	}
	//keys match
	else if(searchkey==d->key)
	{
		cout<<"true\n";
	}
	//if the search key is less than root nodes search key
	else if(searchkey<d->key)
	{
		search(d->left,searchkey);
	}
	//if the search key is greater than root nodes search key
	else
	{
		search(d->right,searchkey);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::preorder_print()
{
	my_bst_node<KT,DT>* temp;
	temp=root;
	preorder_print(temp);
}

template <class KT, class DT>
void my_bst<KT,DT>::preorder_print(my_bst_node<KT,DT>*& f)
{
	if(f!=NULL)
	{
		cout<<f->data<<endl;
		preorder_print(f->left);
		preorder_print(f->right);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::inorder_print()
{
	my_bst_node<KT,DT>* temp;
	temp=root;
	inorder_print(temp);
}

template <class KT, class DT>
void my_bst<KT,DT>::inorder_print(my_bst_node<KT,DT>*& g)
{
	if(g!=NULL)
	{
		inorder_print(g->left);
		cout<<g->data<<endl;
		inorder_print(g->right);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::postorder_print()
{
	my_bst_node<KT,DT>* temp=root;
	postorder_print(temp);
}

template <class KT, class DT>
void my_bst<KT,DT>::postorder_print(my_bst_node<KT,DT>*& n)
{
	if(n!=NULL)
	{
		postorder_print(n->left);
		postorder_print(n->right);
		cout<<n->data<<endl;
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::remove(KT searchkey)
{
	my_bst_node<KT,DT>* temp5=root;
	remov(temp5,searchkey);
}

template <class KT, class DT>
void my_bst<KT,DT>::remov(my_bst_node<KT,DT>*& n, KT deletekey)
{
	if(deletekey<n->key)
	{
		remov(n->left,deletekey);
	}
	else if(deletekey>n->key)
	{
		remov(n->right,deletekey);
	}
	else if(deletekey==n->key)
	{
		deletenode(n);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::deletenode(my_bst_node<KT,DT>*& g)
{
	//if node contains two children
	if((g->left!=NULL)&&(g->right!=NULL))
	{
		cout<<"enter here\n";
		//find max in left subtree
		my_bst_node<KT,DT>* max=findmax(g->left);
		//copy max node data into current node
		g->data=max->data;
		g->key=max->key;
		//delete max node
		remov(max,max->key);
	}
	else
	{
		if(g->left==NULL)
		{
			g=g->right;
			delete g;
		}
		else
		{
			g=g->left;
			delete g;
		}
		
	}
}

template <class KT, class DT>
my_bst_node<KT,DT>* my_bst<KT,DT>::findmax(my_bst_node<KT,DT>* h)
{
	//empty tree
	if(h==NULL)
	{
		return NULL;
	}
	//found max
	if(h->right==NULL)
	{
		return h;
	}
	//recursive call to right subtree since the max would be located on the right
	else
	{
		findmax(h->right);
	}
}

template <class KT, class DT>
int my_bst<KT,DT>::height()
{
	return height(root);
}

template <class KT, class DT>
int my_bst<KT,DT>::height(my_bst_node<KT,DT>* p)
{
	//empty tree
	if(p==NULL)
	{
		return 0;
	}
	//tree not empty go along links
	else
	{
		if(height(p->left)>height(p->right))
		{
			return 1 + height(p->left);
		}
		else
		{
			return 1 + height(p->right);
		}
	}		
}

template <class KT, class DT>
void my_bst<KT,DT>::balanced()
{
	if(balanced(root)==1)
	{
		cout<<"true\n";
	}
	else
	{
		cout<<"false\n";
	}
}

template <class KT, class DT>
bool my_bst<KT,DT>::balanced(my_bst_node<KT,DT>*& j)
{
	if(j==NULL)
	{
		return true;
	}
	else
	{
		if((balanced(j->left)&&balanced(j->right))&&(height(j->left)-height(j->right)==-1)||(height(j->left)-height(j->right)==1)||(height(j->left)-height(j->right)==0))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrderAux(my_bst_node<KT,DT>* t, int level)
{
	if(t) 
	{
		if(level == 1) 
		{
			printf(" %d ", t->key);
		}
		else if (level > 1) 
		{
			printLevelOrderAux(t->left, level-1);
			printLevelOrderAux(t->right, level-1);
		}
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrder(my_bst_node<KT,DT>* t,int height) 
{
	int i;

	for(i = 1; i <=height; i++) 
	{
		printLevelOrderAux(t, i);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::show(int height)
{
	printLevelOrder(root,height);
}


#endif

First the constructor. This is the constructor thats giving you problems :

TreeNode  (Comparable value, TreeNode *leftTree, TreeNode *rightTree) ;

All you have to do is, set the left equal to leftTree and set the right
equal the rightTree. But you should be cautions of that. What if
the root value of the rightTree is not greater than the current Tree?
Then it should not be a rightTree right? The same goes for leftTree.

As for your second question, take a look at this code thats in java.
Its not a binary tree, but a general tree, where a node can
have more than 2 childs, thus we cannot just use a left and right
pointer, but instead we use a list.

public void printPreOrder(){
	if(this == null) 
		return;		
	System.out.print(toString() + " ");		
	ListIterator<GeneralTree<Type>> itr = _children.iterator(); 
	while(itr.hasNext()){
		itr.next().printPreOrder();
	}
}

These are the general steps :
1) Check if the current class is null. If so then return; //base case
2) print current node
3) for each children, printPreOder().

That function should be implemented in the TreeNode class. Hope that helps somewhat.

Edited 6 Years Ago by firstPerson: n/a

First the constructor. This is the constructor thats giving you problems :

TreeNode  (Comparable value, TreeNode *leftTree, TreeNode *rightTree) ;

All you have to do is, set the left equal to leftTree and set the right
equal the rightTree. But you should be cautions of that. What if
the root value of the rightTree is not greater than the current Tree?
Then it should not be a rightTree right? The same goes for leftTree.

As for your second question, take a look at this code thats in java.
Its not a binary tree, but a general tree, where a node can
have more than 2 childs, thus we cannot just use a left and right
pointer, but instead we use a list.

public void printPreOrder(){
	if(this == null) 
		return;		
	System.out.print(toString() + " ");		
	ListIterator<GeneralTree<Type>> itr = _children.iterator(); 
	while(itr.hasNext()){
		itr.next().printPreOrder();
	}
}

These are the general steps :
1) Check if the current class is null. If so then return; //base case
2) print current node
3) for each children, printPreOder().

That function should be implemented in the TreeNode class. Hope that helps somewhat.

I didn't notice an issue with the TreeNode class, but now that you mention it, when I do implement the bst, if the node isn't checking if the values belong on the left/right, it could cause a problem, couldn't it? But lotrsimp12345's code for his node does not include such a check either, so maybe it gets taken care of when inserting?
If I were to try to do it in the TreeNode constructor, it wouldn't be the matter of a simple if statement, would it? Because if the value isn't less than the root, than it shouldn't be on the left. But what if both of the passed TreeNodes are less/greater than the root? They can't both occupy the same pointer, so one would have to be the child of the other?

The constructor that actually confuses me is:

// 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);

	root->left = left.root;

	root->right = right.root;

}

I find it confusing for a couple of reasons. Why is it being passed two trees, instead of two nodes? I think the reason that it confuses me is that the children (or subtrees) of the root are already declared before their parent, which is the tree that is being created by the constructor in question. It confuses me because it just seems backwards. I could see the constructor taking three values, the first being the root, and the following two being set as the sub trees, which could be constructed and have memory allocated for them inside of the constructor. This would seem like a good place to implement that value check to see which value should be the leftsubtree and which should be right.

The second reason it confuses me is: why by value? Shouldn't it be by reference with a pointer? Maybe I'm just not getting it.

the node contains 2 pointers in my case which are left and right and the root node in my bst class is used to scan the tree to do insert, delete, search.

template <class KT, class DT>
void my_bst<KT,DT>::insert(KT searchkey, const DT& newDataItem)
{
	my_bst_node<KT,DT>* temp=new my_bst_node<KT,DT>(searchkey, newDataItem);
	insert(temp, root);
}
 
template <class KT, class DT>
void my_bst<KT,DT>::insert(my_bst_node<KT,DT>*&	newnode ,my_bst_node<KT,DT>*& nodepointer)
{
   //if empty tree
   if(nodepointer==NULL)
   {
		nodepointer=newnode;
   }
   //key less than root nodes 
   else if((newnode->key)<=(nodepointer->key))
   {
	   insert(newnode,nodepointer->left);
   }
   //key greater than root nodes
   else
   {
	   insert(newnode,nodepointer->right);
   }

Edited 6 Years Ago by lotrsimp12345: n/a

Alright I think I may have worked through it, though I still have doubts as to whether its to the teachers liking. He wanted us to add helper methods with parameters to aid in the recursive functions, such as clone, empty, and the traversals, but he wanted us to do it without modifying the class definition. Currently I'm trying to work out the kinks in my non-recursive post order traversal using the stl stack. It's gotten to be quite a mess, and I was wondering if someone could help me get it in working order.

//non-recursive traversal - postorder
template <class Comparable>
void Tree<Comparable>::post()
{
	if (root == NULL)
		return;		//empty tree
	
	TreeNode <Comparable>* cur = root;
	Pair<TreeNode <Comparable> *, int> pair;
	stack<Pair<TreeNode <Comparable> *, int> > stk;
	int flag = 0;
	
	while (cur != NULL)									//process all the nodes on the left until NULL is encountered
	{													//building the stack
		pair = Pair<TreeNode <Comparable> *, int>(cur,0);
		stk.push(pair);
		cur = cur->left;
	}

	while (!stk.empty())								//until the stack is empty
	{
		pair = stk.top();								//store the top pair
		stk.pop();										//pop off the top
		cur = (pair.first);								//vars to the values held by pair
		flag = pair.second;
		if (flag == 0)
		{
			while (cur != NULL)							//process all the nodes on the left until NULL is encountered
			{
				pair = Pair<TreeNode <Comparable> *, int>(cur,0);
				stk.push(pair);
				cur = cur->left;
			}
			pair = stk.pop();											//when null is encountered, pop the last node
			pair.second = 1;											//push it on the stack with a flag of 1
			stk.push(pair);

			if (cur->right != NULL)
			{
				cur = cur->right;
				
				while (cur->left != NULL)
				{
					pair = Pair<TreeNode <Comparable> *, int>(cur->left,0);
					stk.push(pair);
					cur = cur->left;
				}
			}
		}
		else
			cout << cur->item << " ";
	}
	cout << "\n\n End of non-recursive postorder print \n";
}

this is the 'clue' my teacher sent to us to get us started, but im having trouble deciphering what it is he wants in that middle section under (if flag == 0)

template<class Comparable>
void postorderPrint2(TreeNode <Comparable>*root) {
if ( root == NULL ) return ; // empty tree, print nothing
TreeNode <Comparable>* cur = root ;
Pair<TreeNode <Comparable> *, int > pair ;
stack<Pair<TreeNode <Comparable> * , int > > stk ;
int flag = 0 ;
while(cur!= NULL ) {
pair = Pair<TreeNode <Comparable> *, int >(cur,0);
stk.push(pair) ;
cur = cur->left ;
}
while(!stk.empty()) {
pair = stk.top() ; stk.pop() ;
cur = (pair.first) ;
flag = pair.second;
if ( flag == 0 ) {
// just finish process the left subtree, need
// branch to the right , push it back with flag = 1
// if right is not null, then cur = cur->right and
// keep on going left while push nodes onto the stack
// with flag = 0
}
else // now it's time to
print the node ;
}
cout << "\n\n End of non-recursive postorder print \n" ;
}

don't do it with a stack you are typing too much...
use recursion very powerful and easy to understand.

Comments
Recursion is RARELY a good option.

don't do it with a stack you are typing too much...
use recursion very powerful and easy to understand.

Just because you learned recursion recently and it looks kool, it is rarely an acceptable alternative to a loop. Way too many resources are used and you can crash your computer.

Our teacher actually requires us to make 9 different recursive traversals (10 if you include the byLevel one) and three non-recursive traversals. Pre(), In(), and Post(). For Pre, he gave us the code in its entirety, and for In() he gave us enough hints that it took only a short amount of time to apply the code for pre to in. For post order, he changed the structure entirely, storing pairs with flags etc. I'm lost figuring it out. I emailed some of my classmates, and they are having many similar problems with the assignment.

Could anyone help me fix the non-recursive post-order traversal? I Don't have a clue on how to get it working how he wants. It's just confusing the hell out of me.

Also, does anyone know how to add helper methods to a class implementation that are not part of a class's declaration? Because he wants us to add helper methods to make recursive functions possible, but he does not want us adding them to the class declaration of the bt/bst. It just seems like a backwards way of trying to do this assignment...

Edited 6 Years Ago by HoldmysunnyD: n/a

Could anyone help me fix the non-recursive post-order traversal? I Don't have a clue on how to get it working how he wants. It's just confusing the hell out of me.

Also, does anyone know how to add helper methods to a class implementation that are not part of a class's declaration? Because he wants us to add helper methods to make recursive functions possible, but he does not want us adding them to the class declaration of the bt/bst. It just seems like a backwards way of trying to do this assignment...

Google it!! Wiki has a good explanation.

Well I managed to figure out the post order traversal without recursion, but wikipedia wasn't very helpful, though I do appreciate any suggestions ^_^ What I ended up with is

//non-recursive traversal - postorder
template <class Comparable>
void Tree<Comparable>::post()
{
	if (root == NULL)
		return;		//empty tree
	
	TreeNode <Comparable>* cur = root;
	pair<TreeNode <Comparable> *, int> nodePair;
	stack<pair<TreeNode <Comparable> *, int>> stk;
	int flag = 0;											//initialize the flag to 0.
															//the value 0 sets the node to 0, and 1 is for printing
	
	nodePair = pair<TreeNode <Comparable> *, int>(cur, flag);
	stk.push(nodePair);										//initialize the stack with the root node

	while (!stk.empty())									//until the stack is empty
	{
		nodePair = stk.top();								//store the top pair
		stk.pop();											//pop off the top
		cur = (nodePair.first);								//assign cur node pointer to the top node on the stack
		flag = nodePair.second;								//set the flag var to the top nodes var

		if (flag == 1)										//if the node is flagged to be processed
		{
			cout << cur->item << " ";						//print out the value of the node
		}
		else
		{
			nodePair = pair<TreeNode <Comparable> *, int>(cur,1);
			stk.push(nodePair);
			if (cur->right != NULL)
			{
				nodePair = pair<TreeNode <Comparable> *, int>(cur->right,0);
				stk.push(nodePair);
			}
			if (cur->left != NULL)
			{
				nodePair = pair<TreeNode <Comparable> *, int>(cur->left,0);
				stk.push(nodePair);
			}
		}
	}
	cout << "\n\n End of non-recursive postorder print \n";

Now I am still very confused on how my teacher wants me to do the recursive methods without adding extra methods to the class definition. In the class definition, the recursive methods he asks us to implement are

// 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 makeEmpty();

		   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

But he also told me not to modify the class definition. I couldn't figure out how to do recursion with these methods, since they lack all lack a parameter for the current node being worked on. The last three travserals have a pointer to hold the node's parent.

He said, "You can't add those to the declaration of the bt class. But you can add the method as a helper function in the implementation part."

How would one go about this? I've ignored what he said and added those methods, but I will probably get 0 credit if I leave it as is. As far as I know, c++ doesn't support nested functions.

This article has been dead for over six months. Start a new discussion instead.