Learning2Code
Learning2Code

Reputation: 21

How do I copy a binary search tree in pre-order traversal in c++?

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

Answers (1)

john
john

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

Related Questions