递归复制BST的所有树叶到另一个BST

-2

我已经制定出了如何将树叶从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 - >离开递归调用。

来源

2016-11-28 LinearM

它应该工作，小心他们肮脏的细节。它错过了构建完美均衡BST的机会。 – greybeard

尝试一下:)然后询问https://codereview.stackexchange.com/他们认为它:) –

（@FilipHaglund我相信你建议StevenTea在[CR]上呈现它（https：//codereview.stackexchange .com/help/on-topic） - 差不多）。刚注意到这个问题_does not_read_all nodes_。 – greybeard

我不明白这是如何工作的，正如所写。我会用一些缩进呼应这样的：

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步：这会让你的结构不同步;你已经沿着两个分支在源代码树中下了一层，但是你没有在目标树中下降。如果这在你的设置中起作用，那么关于树结构或复制操作的东西还没有在这个算法中。

来源

2016-11-28 18:31:23 Prune

你不必如此重要。当我说“我不明白在哪里通过dest-> right和dest - >留下递归调用时，”我的目标有什么不明白的地方？我的目标只是找出复制所有叶子的正确呼叫。我想到了。 – LinearM

这大部分是OP的后续问题。请确保你正在回答这个问题。请使用评论而不是答案来要求澄清。 –

递归复制BST的所有树叶到另一个BST

回答

相关问题