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