二叉搜索树深度复制和取消引用

Question

我正在尝试为二叉搜索树设置深拷贝构造函数，但似乎无法弄清楚如何处理指针的取消引用。我是 C++ 的新手，开始了解它的工作原理，但这让我很吃惊。

代码如下：

void copyTree_helper(Node **destination,const Node *source)
{
    {
        if(source == NULL)
        {
            (*destination) = NULL;
        }
        else
        {
            (*destination) = new Node;
            (*destination)->data = source->data;
            copyTree_helper(&(*destination)->left, source->left);
            copyTree_helper(&(*destination)->right, source->right);
        }
    }
}

// Creates a binary tree by copying an existing tree
BinarySearchTree::BinarySearchTree(const BinarySearchTree &rhs)
{

    if(&rhs == nullptr)
        root = nullptr;
    else
        copyTree_helper(&(*root), &rhs);

    /*////////////////////////////////////////////
                 Needs implementation
    ////////////////////////////////////////////*/
}

.h 文件中二叉搜索树的实现如下所示。

struct Node
{
    // Data stored in this node of the tree
    std::string data;
    // The left branch of the tree
    Node *left = nullptr;
    // The right branch of the tree
    Node *right = nullptr;
};

现在它不会编译并出现以下错误消息：

BinarySearchTree.cpp:44:9: error: no matching function for call to 'copyTree_helper'
        copyTree_helper(&(*root), &rhs);
        ^~~~~~~~~~~~~~~
BinarySearchTree.cpp:20:6: note: candidate function not viable: no known conversion from 'Node *'
      to 'Node **' for 1st argument
void copyTree_helper(Node **destination,const Node *source)

非常感谢任何帮助我解决问题的帮助或解释。干杯!

Answer 1

问题是您应该传递 &root，而不是 &*root - *root 是 Node，而不是 Node*。

不过，这在函数式编写上要好得多：

Node* copyTree_helper(const Node *source)
{
    if(source == nullptr)
    {
        return nullptr;
    }
    Node* result = new Node;
    result->data = source->data;
    result->left = copyTree_helper(source->left);
    result->right = copyTree_helper(source->right);
    return result;
}

BinarySearchTree::BinarySearchTree(const BinarySearchTree &rhs)
    : root(copyTree_helper(rhs.root))
{
}

或者，如果您向 Node 添加合适的构造函数：

Node* copyTree_helper(const Node *source)
{
    return source == nullptr
          ? nullptr
          : new Node(source->data, 
                     copyTree_helper(source->left), 
                     copyTree_helper(source->right));
}

二叉搜索树深度复制和取消引用

Binary Search Tree Deep copy and dereferencing

c++

deep-copy

binary-search-tree