有沒有更好的方法來迭代克隆N元樹？

Question

我正在尋找更好的或更優化的方法來複制（或在實際問題中，轉換）使用遞歸的n -ryry樹而不使用。是關於我正在試圖解決的一般情況的一些細節如下

• 樹是n元（即高達每一級n個節點）
• 孩子們聯繫到父母和家長有名單所有的孩子
• 在樹中的任何級別，任何節點都可以是葉或分支

我已經想出了以下解決方案。一般的方法是使用兩（三）個堆棧。第一個跟蹤需要處理的原始樹中的項目，第二個跟蹤新創建的副本，以便我們可以適當地分配節點之間的鏈接（這可以分爲兩個堆棧而不是元組，因此可以將三個）。這有效，但它有一些不受歡迎的方面，首先是它感覺非常尷尬。我在想，必須有更好的方法來做到這一點，我錯過了某些東西（或多件事）是顯而易見的。

有沒有人遇到過更直接/更高效的方法？

public TreeNode ConvertTree(TreeNode root) 
{ 
    Stack<TreeNode> processingStack = new Stack<TreeNode>(); 
    Stack<Tuple<Int32, TreeNode>> resultStack = new Stack<Tuple<Int32, TreeNode>>(); 
    TreeNode result = null; 

    processingStack.Push(root); 
    while (processingStack.Count > 0) 
    { 
     var currentProcessingNode = processingStack.Pop(); 
     var parentNode = resultStack.Count > 0 ? resultStack.Pop() : null; 

     // Copies all leaf nodes and assigns parent, if applicable. 
     var newResultNode = CopyNodeData(currentProcessingNode, parentNode != null ? parentNode.Item2 : null); 

     // Push sub-branch nodes onto the processing stack, and keep track of how many for 
     // each level. 
     var subContainerCount = 0; 
     foreach (var subContainer in currentProcessingNode.Children.Where(c => !c.IsLeaf)) 
     { 
      processingStack.Push(subContainer); 
      subContainerCount++; 
     } 

     // If we have have not processed all children in this parent, push it back on and 
     // decrement the counter to keep track of it. 
     if (parentNode != null && parentNode.Item1 > 1) 
     { 
      resultStack.Push(new Tuple<Int32, TreeNode>(parentNode.Item1 - 1, parentNode.Item2)); 
     } 

     // If this node has sub-branches, push the newly copied node onto the result/tracking 
     // stack 
     if(subContainerCount > 0) 
      resultStack.Push(new Tuple<Int32, TreeNode>(subContainerCount, newResultNode)); 

     // The very first time a new node is created, track it to return as the result 
     if (newResultNode.IsRoot) 
      result = newResultNode; 
    } 

    return result; 
} 

請注意，我不尋找一個遞歸解決方案。是的，我意識到它們在許多情況下都是可用的，簡單的和適當的。這個問題更多的是關於如何以迭代的方式有效地完成這種類型的操作，而不僅僅是如何拖延時間。

Answer 1

我會採取一些措施。這假定一個鏈接到父節點，並且你可以檢索一個節點上的子節點數並通過索引訪問一個子節點。

static TreeNode Clone(TreeNode root) 
{ 
    var currentOriginal = root; 
    var currentCloned = Copy(root, null); 
    var clonedRoot = currentCloned; 
    while (currentOriginal != null) 
    { 
     if (currentCloned.Children.Count == currentOriginal.Children.Count) 
     { 
      currentOriginal = currentOriginal.Parent; 
      currentCloned = currentCloned.Parent; 
     } 
     else 
     { 
      var targetChild = currentOriginal.Children[currentCloned.Children.Count]; 
      currentOriginal = targetChild; 
      currentCloned = Copy(currentOriginal, currentCloned); 
     } 
    } 
    return clonedRoot; 
} 


static TreeNode Copy(TreeNode source, TreeNode parent) { ... } 

我們初始化：

• 的工作變量，原樹
• 的工作變量，用於克隆的樹
• 克隆樹的根（使代碼更乾淨，替代方案將返回currentCloned並將第一個if分支中的行更改爲currentCloned = currentCloned.Parent ?? currentCloned）

我們循環，直到我們沒有更多的事情要處理。有兩個選項：孩子的

• 克隆的號碼是一樣的源的兒童人數。這意味着有一個葉節點或所有的孩子已經被處理。上移到父級。
• 克隆的子女比原來少，這意味着應該處理一個或多個孩子，使用上面的索引器技巧處理下一個孩子。

因爲我們可以使用樹本身鏈接到父級，所以不需要任何堆棧來幫助導航。