Implement a function TNode copytreeTNode t that creates a co

Implement a function TNode* copy_tree(TNode* t) that creates a copy of the tree t and returns a pointer to the root of the copy. Test this function by writing a main( that creates a tree and uses the function to create a copy. Print both trees to verify they are the same.

Solution

// BSTree.h #ifndef BSTREE_H #define BSTREE_H #include using namespace std; template struct TNode { TNode(const T &); T data; TNode* left, * right; }; template TNode::TNode(const T & newItem) { data = newItem; left = right = NULL; } template class BSTree { public: enum {T_OK = 0, T_DUPLICATE = -1, T_NOT_FOUND = -2}; BSTree(); BSTree(const BSTree&); ~BSTree(); void clear(); int insert(const T&); int remove(const T&); int height() const; int size() const; void printPreorder() const; void printInorder() const; void printPostorder() const; const BSTree& operator=(const BSTree&); private: TNode * root; void destroyTree(TNode*); int size(TNode*) const; int height(TNode*) const; TNode* copyTree(TNode*); void preTrav(TNode*) const; void inTrav(TNode*) const; void postTrav(TNode*) const; }; template BSTree::BSTree() { root = NULL; } template BSTree::BSTree(const BSTree& treeToCopy) { root = copyTree(treeToCopy.root); } template BSTree::~BSTree() { destroyTree(root); } template void BSTree::destroyTree(TNode* current) { if (current != NULL) { destroyTree(current->left); destroyTree(current->right); delete current; } } template void BSTree::clear() { destroyTree(root); root = NULL; } template int BSTree::insert(const T& newItem) { TNode* current = root, * parent = NULL; while (current != NULL && newItem != current->data) { parent = current; if (newItem < current->data) current = current->left; else // if (newItem > current->data) current = current->right; } if (current != NULL) return T_DUPLICATE; else { TNode* newNode = new TNode(newItem); if (parent == NULL) root = newNode; else if (newNode->data < parent->data) parent->left = newNode; else parent->right = newNode; return T_OK; } } template int BSTree::remove(const T& deleteItem) { TNode* delNode = root, * delParent = NULL, * replNode, * replParent; while (delNode != NULL && deleteItem != delNode->data) { delParent = delNode; if (deleteItem < delNode->data) delNode = delNode->left; else // if (newItem > current->data) delNode = delNode->right; } if (delNode != NULL) { if (delNode->left == NULL) replNode = delNode->right; else if (!delNode->right) replNode = delNode->left; else { replParent = delNode; replNode = delNode-> right; while (replNode->left != NULL) { replParent = replNode; replNode = replNode->left; } if (replParent != delNode) { replParent->left = replNode->right; replNode->right = delNode->right; } replNode->left = delNode->left; } if (delParent == NULL) root = replNode; else { if (delParent->left == delNode) delParent->left = replNode; else delParent->right = replNode; } delete delNode; return T_OK; } else return T_NOT_FOUND; } template int BSTree::size() const { return size(root); } template int BSTree::size(TNode * current) const { if (current != NULL) return 1 + size(current->left) + size(current->right); else return 0; } template < class T > int BSTree::height() const { return height(root); } template int BSTree::height(TNode * current) const { int leftHeight, rightHeight; if (current != NULL) { leftHeight = 1 + height(current->left); rightHeight = 1 + height(current->right); if (leftHeight > rightHeight) return leftHeight; else return rightHeight; } else return 0; } template TNode * BSTree::copyTree(TNode * sourcePtr) { TNode * destPtr; if (sourcePtr != NULL) { destPtr = new TNode(sourcePtr->data); destPtr->left = copyTree(sourcePtr->left); destPtr->right = copyTree(sourcePtr->right); return destPtr; } else return NULL; } template const BSTree & BSTree::operator=(const BSTree & right) { if (this != &right) { destroyTree(root); root = copyTree(right.root); } return *this; } template void BSTree::printPreorder() const { preTrav(root); } template void BSTree::printInorder() const { inTrav(root); } template void BSTree::printPostorder() const { postTrav(root); } template void BSTree::preTrav(TNode * current) const { if (current != NULL) { cout << current->data << \" \"; preTrav(current->left); preTrav(current->right); } } template void BSTree::inTrav(TNode * current) const { if (current != NULL) { inTrav(current->left); cout << current->data << \" \"; inTrav(current->right); } } template void BSTree::postTrav(TNode * current) const { if (current != NULL) { postTrav(current->left); postTrav(current->right); cout << current->data << \" \"; } } #endif