从桌子上给树浇水

本文关键字： | 更新日期: 2023-09-27 18:12:00

我有一个包含所有节点的DataTable。它们被序列化到数据库中。我想创建数据的对象图(分层)表示。似乎有几种方法可以做到这一点。

本文描述了一种高阶方法(意味着在树完全构建之前需要对DataTable进行大量搜索)

是否存在Order-N方法?在我的例子中，我已经将DataTable中树的节点预先排序成有序的形式。意思是，第一行显示父节点的NULL，因为它是根节点。后面的每一行都按顺序排序。

我似乎想起了我学生时代的一种Order-N方法。但是我记不起来了。

我的DataTable模式如下:

NodeID - int
ParentNodeId - null
数据-字符串

从桌子上给树浇水

这是一个算法，它应该做你需要它做的事情。它假设您的数据是有序的，所以它在O(n)内执行。

首先，您需要一个像这样的节点:

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

加载第一行为current
加载下一行;比较newRow.ParentNodeId和current.NodeId
直到找到匹配，设置current = current.Parent
将newRow添加到current.Children中，并将current设置为新行
转到步骤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;
}