Алгоритм реорганизовать структуру дерева

Question

У меня есть дерево, как это:

ABCDEF 
/ \ 
    ABC  DEF 
/ \ /| \ 
A BC D E F 
    /\ 
    B C 

Каков алгоритм, чтобы привести его в следующей форме?

  ABCDEF 
     / \ 
     ABCDE F 
    / \ 
     ABCD E 
    / \ 
    ABC D 
/ \ 
    BC A 
/\ 
B C 

EDIT:
Идея заключается в том, чтобы сначала взять B. Затем узел выполняет свою работу с C, поэтому вы получаете BC.
Затем используйте BC и выполните свою работу с A, чтобы получить ABC.
Продолжить вверх ...

Я не смог найти документацию по этому вопросу.

фона:
Я пытаюсь использовать это для выражения фильтра. Выражение может содержать несколько токенов, которые связаны с оператором.

Я использую следующий класс для этого:

public class FilterNode { 
    // Node information 
    FilterNode next; 

    bool Match(...) { ... } 
} 

Цель состоит в том, что узел способен выполнять бинарную операцию с this и next.

Answer 1

Итак, важно то, что здесь важно упорядочить узлы по глубине, а затем их первоначальным порядком слева направо.

Поскольку вы не определить Node класс, я использовал следующие шахтное:

public class Node 
{ 
    public Node() 
    { 
     Children = new List<Node>(); 
    } 
    public string Value { get; set; } 
    public List<Node> Children { get; set; } 
} 

Первое, что мы хотим сделать, это создать метод для обхода дерева. Нам нужны все листовые узлы (без каких-либо нелистовых узлов), и мы также хотим знать глубину каждого узла. Это достаточно просто изменить традиционный алгоритм обхода соответственно:

public static IEnumerable<Tuple<Node, int>> TraverseLeavesWithDepth(Node root) 
{ 
    var queue = new Queue<Tuple<Node, int>>(); 
    queue.Enqueue(Tuple.Create(root, 0)); 

    while (queue.Any()) 
    { 
     var next = queue.Dequeue(); 
     foreach (var child in next.Item1.Children) 
     { 
      queue.Enqueue(Tuple.Create(child, next.Item2 + 1)); 
     } 

     if (!next.Item1.Children.Any()) 
      yield return next; 
    } 
} 

Теперь это ширина первого поиска, что означает, что они на самом деле в обратном порядке глубины, но мы исправим это позже.

Теперь, чтобы создать новое дерево.Мы можем взять результаты нашего предыдущего метода и просто упорядочить по глубине (по убыванию), чтобы получить нужные нам предметы в том порядке, в котором они нам нужны.

Оттуда мы просто перебираем результаты, беря каждый лист, связывая его с предыдущим узлом, а затем создаем нового родителя для представления этой пары (а затем используя этот родительский элемент как новый «предыдущий» узел).

public static Node Straighten(Node root) 
{ 
    var nodes = TraverseLeavesWithDepth(root) 
     .OrderByDescending(pair => pair.Item2) 
     .Select(pair => pair.Item1); 

    using (var iterator = nodes.GetEnumerator()) 
    { 
     if (!iterator.MoveNext()) 
      return null; 

     var previous = iterator.Current; 

     while (iterator.MoveNext()) 
     { 
      var next = iterator.Current; 
      var parent = new Node(); 
      parent.Value = new string(previous.Value 
       .AsEnumerable().Concat(next.Value) 
       .OrderBy(c => c) 
       .ToArray()); 

      parent.Children.Add(previous); 
      parent.Children.Add(next); 

      previous = parent; 
     } 

     return previous; 
    } 
} 

Фактическое строительство узлов, вероятно, различаются в зависимости от реализации узла (и вы также можете воссоздать листья, а не ссылки на старые, как я).

Answer 2

Что делать, если 1/вы посещаете дерево и получить все листья в списке, а затем 2/Вы можете упорядочить список так, как вы хотите (по желанию) 3/запускать список и объединить результат:

 var leaves = new List<Node>(); 
     Node root = null;//Todo : init correctly 
     foreach(var leave in leaves) 
     { 
      root = new Node(root,leave); 
     } 

Answer 3

Возьмите одну из букв, которые больше всего присутствуют в исходном дереве, например, B, и найдите другие буквы, которые появляются одинаковое количество раз, например, C. Объедините их вместе и получите BC.

Затем найдите одну из букв, которые меньше всего выглядят в исходном дереве, например, A, D, E, F, построить объединенный узел BCA, если мы возьмем A на этот раз.

Затем выберите один из D, E, F, постройте BCAD, если мы возьмем D на этот раз и т. Д.?