遞歸複製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

回答

相關問題