Дерево комбинаций и разбиений

Question

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

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

Я сделал этот иллюстрированный образец:

       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" из всех моих комбинаций слева направо.

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

Answer 1

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

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

Скажем, у нас есть класс 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 result;
}
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 (), теперь нет необходимости в средствах сравнения на равенство.

Answer 2

Если я вас понимаю - ваше дерево выглядит (потенциально) так, где . обозначает узел с дочерними элементами, но без «содержимого», а 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"

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