Should be a simple?......Binary Tee....passing of parameters...

I recentley have been learning about binary trees and have been trying to learn each one of these functions but one of them I am having trouble with.... That function is copyTree... Hear is the code...all of it works but I don't know what I am suppose to list as my arguments when I call copyTree() from main....

Code:

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include "string"
#include <cassert>
#include <iostream>

using namespace std;

template <class elemType>
struct nodeType
{
	elemType			info;
	nodeType<elemType>  *llink;
	nodeType<elemType>  *rlink;
};
	
template <class elemType>
class binaryTreeType
{
public:
    const binaryTreeType<elemType>& operator=
                 (const binaryTreeType<elemType>&); 
    void copyTree(nodeType<elemType>* &copiedTreeRoot,
                  nodeType<elemType>* otherTreeRoot);HELP see main
    bool isEmpty() const;
    void inorderTraversal() const;
    void preorderTraversal() const;
    void postorderTraversal() const;
    int treeHeight() const;
    int treeNodeCount() const;
    int treeLeavesCount() const;
    void destroyTree();
    void printTree();
    void printTree(nodeType<elemType> *p);
    void printTreeNode(string label, nodeType<elemType> *p);
    binaryTreeType(const binaryTreeType<elemType>& otherTree); 
    binaryTreeType();   
    ~binaryTreeType();   

protected:
    nodeType<elemType>  *root;

private:

    void destroy(nodeType<elemType>* &p);
    void inorder(nodeType<elemType> *p) const;
    void preorder(nodeType<elemType> *p) const;
    void postorder(nodeType<elemType> *p) const;
    int height(nodeType<elemType> *p) const;
    int max(int x, int y) const;
};

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
	return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
	inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
	preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
	postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
	return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
	return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
	return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
                      (nodeType<elemType>* &copiedTreeRoot,
		               nodeType<elemType>* otherTreeRoot)
{
	if (otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
	}
} //end copyTree


template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p) const
{
	if (p != NULL)
	{
		inorder(p->llink);
		cout << p->info << " ";
		inorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p) const
{
	if (p != NULL)
	{
		cout << p->info << " ";
		preorder(p->llink);
		preorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p) const
{
	if (p != NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout << p->info << " ";
	}		
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
           operator=(const binaryTreeType<elemType>& otherTree)
{ 
	if (this != &otherTree) //avoid self-copy
	{
		if (root != NULL)  //if the binary tree is not empty, 
			              //destroy the binary tree
			destroy(root);

		if (otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
	}//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
	if (p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
	}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
	destroy(root);
}

	//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
              (const binaryTreeType<elemType>& otherTree)
{
	if (otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
	destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p) const
{
	if (p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
	if (x >= y)
		return x;
	else
		return y;
}

template<class elemType>
void binaryTreeType<elemType>::insert(const elemType& insertItem)
{
    nodeType<elemType> *current;  //pointer to traverse the tree
    nodeType<elemType> *trailCurrent; //pointer behind current
    nodeType<elemType> *newNode;  //pointer to create the node

    newNode = new nodeType<elemType>;
    assert(newNode != NULL);
    newNode->info = insertItem;
    newNode->llink = NULL;
    newNode->rlink = NULL;

    if (root == NULL)
       root = newNode;
    else
    {
       current = root;
 
       while (current != NULL)
       {
           trailCurrent = current;

           if (current->info == insertItem)
           {
               cout << "The item to be inserted is already in ";
               cout << "the list -- duplicates are not allowed."
                    << endl;
               return;
           }
           else
               if (current->info > insertItem)
                   current = current->llink;
               else
                   current = current->rlink;
       }//end while

       if (trailCurrent->info > insertItem)
           trailCurrent->llink = newNode;
       else
           trailCurrent->rlink = newNode;
   }
}//end insert


template<class elemType>
void binaryTreeType<elemType>::printTree()
{
	printTree(root);
}

template<class elemType>
void binaryTreeType<elemType>::printTree(nodeType<elemType> *p)
{
    cout << "    root:  " << p->info << endl;
    printTreeNode("left", p->llink);
    printTreeNode("right", p->rlink);
}

template<class elemType>
void binaryTreeType<elemType>::printTreeNode(string label, nodeType<elemType> *p)
{
	if(p != NULL)
    {
		cout << "    " << label << "  " << p->info;
        printTreeNode("left:", p->llink);
        printTreeNode("right:", p->rlink);
        cout << endl;
    }
}

#endif

void main()
{
	binaryTreeType<int> treeRoot;
	int num;

	cout << "You are going to populate the tree now" << endl;
	cout << "Enter a number then hit enter. This will add the number to the tree" << endl;
	cout << "When you don't want to enter anymore numbers" <<endl; 
	cout << "into the tree type -1111 and hit enter" << endl << endl;
	cout << "Enter Numbers now" <<endl;
	cin >> num;

	while (num != -1111)
	{
		treeRoot.insert(num);
		cin >> num;
	}

	cout << endl << "Tree nodes in inorder sequence: ";
	treeRoot.inorderTraversal();

	cout << endl << "Tree nodes in preorder sequence: ";
	treeRoot.preorderTraversal();

	cout << endl << "Tree nodes in postorder sequence: ";
	treeRoot.postorderTraversal();
	cout << endl;
	cout << "Tree Height: " << treeRoot.treeHeight()
		 << endl << endl;
	cout << "Tree in current state" << endl;
	treeRoot.printTree();
	
	treeRoot.copyTree(? 2 arguments but what);HELP

	treeRoot.printTree();
}

It looks like a pointer to the root node and then...ahh who am I kidding I really don't know....any insight would be great...

Thanks

Chad

Don't use void main. Use int main and add return 0; to the end.

Code:

nodeType<elemType>* &copiedTreeRoot,

Is it a pointer or a reference? Make up your mind.

If it's a pointer:

Code:

treeRoot.copyTree(&treeRoot, ...);

A reference:

Code:

treeRoot.copyTree(treeRoot, ...);

>> Is it a pointer or a reference? Make up your mind.

It's a reference to a pointer, which is a perfectly valid way of modifying what a pointer points to in a function.

You can create a nodeType pointer variable and pass it to the function. When the function returns, it will point to the copied tree, and then you will have to delete it in the main code.

Originally Posted by Daved

>> Is it a pointer or a reference? Make up your mind.

It's a reference to a pointer, which is a perfectly valid way of modifying what a pointer points to in a function.

You can create a nodeType pointer variable and pass it to the function. When the function returns, it will point to the copied tree, and then you will have to delete it in the main code.

Still a little bit confused....


nodeType<int> * current;
nodeTYpe<int> * copy:

?

It really depends on what you want to do. The copyTree method is a bit odd in that it is a member of the binaryTree class but ignores the data of the binaryTree that it is called from. You could pass copy from your text above by just passing it directly. What you would pass as the second parameter is a little more confusing. Look at the code in the operator=. It calls copyTree perfectly. That seems to be the intended usage... internal copying of one tree's data to another. Im not sure why you would want to call it from main, you'd have to be more clear on what you are trying to accomplish with that.

Well, basically this is all a learning excersie for me. I am trying to rip these functions apart in my head to learn more about the binary tree. As far as accessing the the copyTree goes I am more intrested in basically making it work and understand why it works. So with that in mind all I am simply tyring to do is copy the tree into a tempTree and print it back out to me. I guess a more better way to confirm this is if maybe I swapped the left and right subTrees like this.

Code:

template <class elemType>
void binaryTreeType<elemType>::swapTree
                      (nodeType<elemType>* &copiedTreeRoot,
		               nodeType<elemType>* otherTreeRoot)
{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;  //first time it get the root
		copiedTreeRoot->info = otherTreeRoot->info;
		//I am swapping this so when I do print the 
               //tree back to me the subtrees will be swapped.  It is strickly for conformation...
		swapTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
		
		swapTree(copiedTreeRoot->llink, otherTreeRoot->llink);

	}
} //end copyTree

Like I said my whole goal now is to populate the tree, print the tree, copy the tree (i.e. swapTree), and print new swapped subtree tree. I have all the way to the copy part down.