有没有更好的方法来迭代克隆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）

我们循环，直到我们没有更多的事情要处理。有两个选项：孩子的

• 克隆的号码是一样的源的儿童人数。这意味着有一个叶节点或所有的孩子已经被处理。上移到父级。
• 克隆的子女比原来少，这意味着应该处理一个或多个孩子，使用上面的索引器技巧处理下一个孩子。

因为我们可以使用树本身链接到父级，所以不需要任何堆栈来帮助导航。