递归复制BST的所有树叶到另一个BST
问题描述:
我已经制定出了如何将树叶从BST复制到另一个BST的算法。递归复制BST的所有树叶到另一个BST
- 检查如果树空
- 如果我们到达叶,将数据复制到目标BST。
- 调用与源BST - >左和源BST - >右递归函数与目的地的指针各自的方向
- 否则,递归调用没有dest - >左或dest - >右(因为我们会去为空)。
该算法是否可行?
434 int copy_leaves(node * source, node * & dest)
435 {
436 if (!source)
437 {
438 dest = NULL;
439 return 0;
440 }
441
442 if (!(source -> left) && !(source -> right))
443 {
444 dest = new node;
445 dest -> data = source -> data;
XXX dest -> left = dest -> right = NULL;
446 }
447
448 return copy_leaves(source -> left, dest) + //???
449 copy_leaves(source -> right, dest) + 1; //???
450 }
好吧我试着实现我的算法,并有几个故障。我不知道在哪里做递归调用。我知道我在两次调用后到达null(然后我们知道该节点是叶),这意味着我复制数据。我不明白在哪里传递dest-> right和dest - >离开递归调用。
答
我不明白这是如何工作的,正如所写。我会用一些缩进呼应这样的:
BST_copy(src, dst)
# step 1
if tree is empty
<action not specified; assume return>
else
# step 2
if src is a leaf
copy data to the destination tree
# step 3
BST_copy(src->left, dst->left)
BST_copy(src->right, dst->right)
#step 4
else
BST_copy(src->left, dst)
BST_copy(src->right, dst)
- 第1步:你有没有指定的操作;请填写。
- 步骤2:目标树是否已经具有与源树相同的完整结构?如果不是,你如何管理该副本?
- 步骤3:如果树是叶子,则没有剩下&右子树;为什么当你知道链接是null?
- 第4步:这会让你的结构不同步;你已经沿着两个分支在源代码树中下了一层,但是你没有在目标树中下降。如果这在你的设置中起作用,那么关于树结构或复制操作的东西还没有在这个算法中。
+0
你不必如此重要。当我说“我不明白在哪里通过dest-> right和dest - >留下递归调用时,”我的目标有什么不明白的地方?我的目标只是找出复制所有叶子的正确呼叫。我想到了。 – LinearM
+0
这大部分是OP的后续问题。请确保你正在回答这个问题。请使用评论而不是答案来要求澄清。 –
它应该工作,小心他们肮脏的细节。它错过了构建完美均衡BST的机会。 – greybeard
尝试一下:)然后询问https://codereview.stackexchange.com/他们认为它:) –
(@FilipHaglund我相信你建议StevenTea在[CR]上呈现它(https://codereview.stackexchange .com/help/on-topic) - 差不多)。刚注意到这个问题_does not_read_all nodes_。 – greybeard