Есть ли лучший способ клонировать N-арное дерево итеративно?

Question

Я ищу лучший или более оптимизированный метод для копирования (или в фактической проблеме, преобразования) n-арного дерева без с использованием рекурсии. Некоторые подробности, касающиеся общей ситуации, что я пытаюсь решить следующие

• Дерево п-арной (т.е. до п узлов на уровне)
• Дети имеют ссылку на родителя и родитель имеет список все дети
• В любом заданном уровне дерева, любой узел может быть лист или ветвь

Я придумал следующее решение. Общий подход заключается в использовании двух (трех) стеков. Первый отслеживает элементы из исходного дерева, которые необходимо обработать, а второй отслеживает только что созданные копии, чтобы мы могли соответствующим образом назначить привязку между узлами (это можно разделить на два стека вместо Tuples, следовательно, три). Это работает, но у него есть ряд нежелательных аспектов, первый из которых заключается в том, что он просто чувствует себя невероятно неудобно. Я думаю, что должен быть лучший способ сделать это, и я пропускаю что-то (или несколько вещей, которые являются) очевидными.

Кто-нибудь сталкивался с чем-то более прямым или более эффективным подходом?

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) { ... } 

Инициализирует:

• A рабочего переменный, для исходного дерева
• рабочего переменным, для клонированного дерева
• Корня клонированного дерева (так что код чище , альтернативой было бы возвращение currentCloned и изменение линии в первом отрезке if до currentCloned = currentCloned.Parent ?? currentCloned)

Мы зацикливаемся до тех пор, пока нам нечего больше обрабатывать. Существует два варианта:

• Число детей клона совпадает с количеством детей в источнике. Это означает, что есть либо листовой узел, либо все дети обработаны. Переместитесь к родительскому.
• Клон имеет меньше детей, чем оригинал, это означает, что один или несколько детей должны быть обработаны, обработайте следующего ребенка, используя трюк индексатора выше.

Поскольку мы можем ссылаться на родителя с использованием самого дерева, никакие стеки не нужны для навигации.