如何在c++中复制一个预序遍历的二叉搜索树？

af7jpaap 于 2022-11-19 发布在其他

关注(0)|答案(1)|浏览(165)

我试图在C++中将一个BST复制到另一个BST，但是不知道如何在前序遍历中进行。我在下面附上了一张图片，上面是我尝试过但没有成功的图片。我只是不断地抛出分段错误。我必须用我展示的两个函数来完成它。第一个函数是在public中，它调用了在private中的void副本。

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;
}

下面是提供的.H文件，无论如何都不能更改。

#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;
};

c++

来源：https://stackoverflow.com/questions/74449017/how-do-i-copy-a-binary-search-tree-in-pre-order-traversal-in-c

1条答案

按热度按时间

fcg9iug31#

最大的问题是一个复制的函数必须返回那个副本，但是你的copy函数是void，这就是为什么你不能让它工作。
像这样的东西

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;
    }
}

编辑

显然，copy函数和类的签名通常是不可协商的。因此，我们将编写另一个执行真实的工作的函数，并从copy调用该函数。如下所示

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;
    }
}

这里我们使用了一个额外的函数real_copy，但是由于该函数不是类的一部分，并且是实现源文件的本地函数，因此不必编辑头文件。

赞(0）回复(0）举报 2022-11-19

我来回答

如何在c++中复制一个预序遍历的二叉搜索树？

1条答案

相关问题

热门标签

最新问答