我正试图将叶(递归)从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
由于已经在注释中发现了错误,因此这里有一个经过表面测试的解决方案。
不能盲目复制节点;您需要创建一个BST结构
您可以先将叶子向左和向右复制,然后以适当的方式将它们连接起来。
由于从BST开始,左侧副本中最大的节点小于右侧副本中最小的节点
这意味着,如果将右副本中最左边的指针(为null)替换为左副本的根,则将获得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
也可以为您提供最左边的节点,这样可以节省一些自上而下的遍历,但它会使代码复杂化,所以我将其作为练习。
void copy_leaves(node * src, node *& dest)
{
if (!src) return;
dest = new node(src->data); // this should zero out the pointers, assuming you make one.
copy_leaves(src->left, dest->left);
copy_leaves(src->right, dest->right);
}