Увлажняйте дерево со стола

Question

У меня есть DataTable со всеми моими узлами в нем.Они были сериализованы в базу данных.Я хочу создать граф объектов (иерархическое) представление данных.Кажется, есть несколько способов сделать это.

В этой статье описан метод высокого порядка (то есть, он требует много поиска в DataTable, прежде чем дерево будет полностью построено)

Есть ли подход Order-N? В моем случае я предварительно отсортировал узлы дерева в DataTable в форму заказа.Это означает, что первая строка показывает NULL для родителя, потому что это корень.Каждая последующая строка сортируется в по порядку записи .

Мне кажется, я вспоминаю подход Order-N со своих школьных дней.Но я не могу вспомнить.

Моя схема DataTable похожа на это:

• NodeID - int
• ParentNodeId - nullable
• Data - string

Answer 1

Вот алгоритм, который должен делать то, что вам нужно.Предполагается, что ваши данные в порядке, поэтому он выполняет в O (n).

Во-первых, вам нужен узел, который выглядит следующим образом:

class Node {
    Node Parent;
    List<Node> Children = new List<Node>();
    int NodeId;
    string Data;
    public Node(NodeRow row) { ... }
}

1. Загрузить первую строку как current.
2. Загрузить следующую строку;сравните newRow.ParentNodeId с current.NodeId.
3. Пока не найдете совпадение, установите current = current.Parent
4. Добавьте newRow к current.Children и установите current в новой строке.
5. Перейти к шагу 2.

Вот и все!Если ваши данные гарантированно правильно структурированы, вам не нужно делать никаких дополнительных null проверок.

Образец:

Node CreateTree(IEnumerable<NodeRow> rows) {
    Node root = null;
    Node current = null;
    foreach (var row in rows) {
        // Root:
        if (root == null) { 
            root = current = new Node(row);
            continue;
        }
        // Traverse up the tree until the parent is found:
        while (row.ParentNodeId != current.NodeId) {
            current = current.Parent;
        }
        // Add the new node as a child of the current one:
        var rowNode = new Node(row);
        rowNode.Parent = current;
        current.Children.Add(rowNode);
        current = rowNode;
    }
    return root;
}