c++ - 在 C++ 中从二叉搜索树(递归)复制叶子

Question

我正在尝试将叶子(递归地)从 BST 复制到仅包含复制的叶子的新 BST。这是我所做的:

27 void tree::copy_leafs(node * src, node *& dst) {
28     if (!src)                                 //Case 1: current node is NULL
29         return;
30     if (!src->left && !src->right) {          //Case 2: current node is a leaf
31         dst = new node;
32         dst->data = src->data;
33         dst->left = NULL;
34         dst->right = NULL;
35         copy_leafs(src->left, dst->left);
36         copy_leafs(src->right, dst->right);
37     } else {                                  //Case 3: current node is NOT a leaf
38         copy_leafs(src->left, dst);
39         copy_leafs(src->right, dst);
40    }
41 }

在编译、访问叶子和复制叶子时，代码似乎是正确的。然而，新树的根 (dst) 总是只有一片叶子(最后一片叶子)。有什么想法吗？

问题的EX:

• 假设 src 有这些叶子:4 15 19 23
• 执行此函数后，dst 将只有 23。

Answer 1

由于已经在评论中发现了错误，这里有一个经过非常表面测试的解决方案。

不能盲目复制节点；你需要创建一个 BST 结构。
为此，您可以先将叶子复制到左侧，然后将叶子复制到右侧，然后以合适的方式加入它们。

由于您从 BST 开始，因此左侧拷贝中的最大节点小于右侧拷贝中的最小节点。
这意味着如果将右拷贝中最左边的左指针(为空)替换为左拷贝的根，您将获得 BST。

当然，这可能会导致一棵非常不平衡的树。
如果你想平衡它，你需要一个更复杂的解决方案，留作练习。

假设这个节点结构:

struct node
{
    int datum;
    node* left;
    node* right;
    node(int v) : datum(v), left(nullptr), right(nullptr) {}
};

它看起来像这样:

node* copy_leaves(const node* tree)
{
    if (!tree)
    {
        return nullptr;
    }
    if (!tree->left && !tree->right)
    {
        return new node(tree->datum);
    }

    // Not a leaf; recurse
    node* left_leaves = copy_leaves(tree->left);
    node* right_leaves = copy_leaves(tree->right);
    if (!left_leaves)
    {
        return right_leaves;
    }
    else if (!right_leaves)
    {
        return left_leaves;
    }
    else
    {
        // Locate the leftmost node in the right tree.
        node* smallest_right = right_leaves;
        while (smallest_right->left != nullptr)
        {
            smallest_right = smallest_right->left;
        }
        // And attach the left leaf tree.
        smallest_right->left = left_leaves;
        return right_leaves;
    }
}

我相信可以让 copy_leaves 也给你最左边的节点，这样可以节省一些自上而下的遍历，但它会使代码复杂化，所以我把它留作练习。