Reputation: 21
I am trying to copy one BST to another BST in c++ but can't figure out how to do it in pre-order traversal. I have attached an image below of what I have tried with no success. I just keep getting segmentation faults thrown. I must do It with the two functions I have show. The first one is in public which calls out to the void copy that is in private.
BST::BST(const BST &obj):root{nullptr}
{
copy(obj.root);
}
void BST::copy(const TNodePtr Tree)
{
TNodePtr tempTree = new (nothrow) TNode;
tempTree = nullptr;
if (Tree == nullptr){
cout << "No elements in tree. " << endl;
}else if(Tree->left != NULL)
{
tempTree->element = Tree->element;
copy(Tree->left);
copy(Tree->right);
}
delete tempTree;
}
Below is the provided .H file that can't be altered what-so-ever.
#pragma once // alternative Guard format
#include <string>
typedef std::string TElement;
struct TNode;
typedef TNode * TNodePtr;
struct TNode {
TElement element;
TNodePtr left, right;
};
class BST {
public: // exportable
// General description of each of the ADT operations/functions – exportable operations only
BST();
BST( const BST & );
~BST();
void insert( const TElement );
void remove( const TElement );
TNodePtr search( const TElement ) const;
void preView() const;
void inView() const;
void postView() const;
private: // non-exportable
// No private member documentation – implementation details are hidden/abstracted away
TNodePtr root;
void copy( const TNodePtr );
void destroy( TNodePtr & );
void removeNode( TNodePtr & );
void findMinNode( TNodePtr &, TNodePtr & );
void insert( const TElement, TNodePtr & );
void remove( const TElement, TNodePtr & );
TNodePtr search( const TElement, const TNodePtr ) const;
void preView( const TNodePtr ) const;
void inView( const TNodePtr ) const;
void postView( const TNodePtr ) const;
};
Upvotes: 0
Views: 316
Reputation: 88092
The big problem is that a function which makes a copy has to return that copy. But your copy
function is void
. That's why you can't make it work.
Something like this
BST::BST(const BST& obj) : root(copy(obj.root))
{
}
TNodePtr BST::copy(TNodePtr Tree)
{
if (Tree == nullptr)
{
return nullptr;
}
else
{
TNodePtr node = new TNode();
node->element = Tree->element;
node->left = copy(Tree->left);
node->right = copy(Tree->right);
return node;
}
}
EDIT
Apparently the signature of the copy
function and class generally is non-negotiable. So we'll write another function which does the real work, and call that function from copy
. Like this
static TNodePtr real_copy(TNodePtr Tree);
BST::BST(const BST& obj) : root(nullptr)
{
copy(obj.root);
}
void BST::copy(const TNodePtr Tree)
{
root = real_copy(Tree);
}
static TNodePtr real_copy(TNodePtr Tree)
{
if (Tree == nullptr)
{
return nullptr;
}
else
{
TNodePtr node = new TNode();
node->element = Tree->element;
node->left = real_copy(Tree->left);
node->right = real_copy(Tree->right);
return node;
}
}
Here's we are using an additional function real_copy
but since that function is not part of your classes and is local to your implementation source file you don't have to edit the header file.
Upvotes: 1