Блог

У меня есть (недвоичное) дерево, содержащее записи со строками.

Я хотел бы создать массивы записей (или указателей на записи), содержащие данные, следующим образом…

Я сделал этот иллюстрированный пример:

        ABCDEFGHIJKL
      /     |      
   ABC      DE      FGHIJKL
  /               /   |   
AB     C        FGH   IJK   L
                      / 
                     I  JK
 

Результат должен быть:
(7 массивов, содержащих записи с этими данными)

1. ABCDEFGHIJKL
2. ABC, DE, FGHIJKL
3. ABC, DE, FGH, I, JK, L
4. ABC, DE, FGH, IJK, L
5. AB, C, DE, FGHIJKL
6. AB, C, DE, FGH, I, JK, L
7. AB, C, DE, FGH, IJK, L

Некоторые примечания:

• Меня не волнует порядок результатов (1-7), пока я получаю их все.
• Я работаю с C#
• В этом примере есть 4 уровня с 7 путями, но в реальной жизни это может быть любое количество уровней.
• Шаблон здесь создается "ABCDEFGHIJKL" из всех моих комбинаций слева направо.

У кого-нибудь есть предложения?

Идея проста. Создайте список, содержащий только корневой узел, затем замените его дочерними элементами. Затем рекурсивно замените каждый узел в этом списке и добавьте этот список в коллекцию результатов при каждой операции замены.

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

Допустим, у нас есть класс Tree с узлами класса Node (у каждого узла есть Children ). Корень дерева есть Root . Затем вы можете реализовать свою функцию следующим образом (внутри Tree класса):

 public List<List<Node>> GetLevels() {
    List<Node> nodes = new List<Node>();
    nodes.Add(Root);
    List<List<Node>> result = new List<List<Node>>();
    GetLevelsCore(nodes, result);
    return resu<
}
void GetLevelsCore(List<Node> nodes, List<List<Node>> result) {
    if(result.Any(list => list.SequenceEqual(nodes))) return;
    result.Add(nodes);

    foreach(Node node in nodes) {
        if(node.Children.Count != 0) {
            List<Node> replacedNodes = new List<Node>(nodes);
            int index = replacedNodes.IndexOf(node);
            replacedNodes.RemoveAt(index);
            replacedNodes.InsertRange(index, node.Children);

            GetLevelsCore(replacedNodes, result);
        }
    }
}
 

Результаты, которые я получил:

 List<List<Node>> result = tree.GetLevels();
List<string> strings = new List<string>(result.Select(nodes => string.Join(", ", nodes.Select(node => node.Value))));
 

strings :

1. «ABCDEFGHIJKL»
2. «ABC, DE, FGHIJKL»
3. «AB, C, DE, FGHIJKL»
4. «AB, C, DE, FGH, IJK, L»
5. «AB, C, DE, FGH, I, JK, L»
6. «ABC, DE, FGH, IJK, L»
7. «ABC, DE, FGH, I, JK, L»

UPD: замененный содержит проверку с помощью Any(), теперь нет необходимости в средствах сравнения равенства.

Если я вас понимаю, ваше дерево выглядит (потенциально) примерно так, где a . указывает на узел с дочерними элементами, но без «содержимого», и AB указывает на узел с текстовым содержимым «AB».

                                        .
                                 /     |       
                                .      DE     .
                               /          /   |   
                             AB    C      FGH  .    L
                                              / 
                                             I  JK
 

т. е.: Один корневой узел с 3 дочерними узлами (1 — лист, содержащий текст «DE»).

Я предполагаю, что у вас уже есть ваша структура данных, которая будет представлять собой дерево, где каждый узел может иметь 3 дочерних узла, один родительский и необязательное текстовое поле. Что — то вроде:

 class Node
{
    // NB: I would not implement the class exactly like this - for illustrative purposes only.
    Node Left;
    Node Mid;
    Node Right;
    string Text;
}
 

Чего вы хотите добиться, так это пройти по дереву и объединить весь текст на определенном уровне или ниже определенного уровня?

Итак, что-то вроде,

• уровень 4: I JK = «IJK»
• уровень 3: AB C FGH (I JK) L = «ABCDFGHIJKL»
• уровень 2: (AB C) DE (FGH (I JK) L) = «ABCDEFGHIJKL»

Чтобы работать с деревьями таким образом, вам, вероятно, придется использовать рекурсию. Вам нужно будет написать рекурсивную функцию для поиска нужных вам узлов, Отслеживания глубины и т. Д. И Выполнения операций с текстом / данными, которые вы хотите.

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

Например, очень простая рекурсивная функция, которая просто находит вам текст всех узлов определенного уровня, может выглядеть примерно так:

 //NB: Comes with no warrentee and untested :).
public string TextAtLevel(Node root, int maxLevel, int currentLevel)
{
    currentlevel  = 1;

    if(currentLevel == maxLevel)
    {
        // stop the recursion, return text of this node
        return root.Text;
    }
    else
    {
         //Recurse into the child nodes. Left to right, depth first.
         return TextAtLevel(root.Left, maxLevel, currentLevel)   
                TextAtLevel(root.Mid, maxLevel, currentLevel)   
                TextAtLevel(root.Right, maxLevel, currentLevel)
    }

}

Node treeRoot = LoadData(); // imagine tree being populated as per diagram.
string textAtLevel4 = TextAtLevel(treeRoot, 4, 0); // returns "IJK"
 

Надеюсь, это поможет вам начать работу.