0

假设我有一个代表嵌套集层次结构的节点列表（示例在伪 c# 中）。

class Node
{
    public decimal left;
    public decimal right;
    public decimal id;
    public void AddChild(Node child) {...}
    ...
}

List<Node> nodes = GetFlatNodesWithoutChildrenSetFromDatabase();

字段left和被填充right，id因为这些值存储在某个数据库中。

将这个平面列表转换为层次结构的有效方法是什么，这意味着为每个父节点填充适当的子节点？

一种方法是找到每个节点的所有祖先，对它们进行排序以找到父节点并将子节点添加到该节点。

foreach (var n in nodes)
{
    var parent = nodes.Where(i => i.left < n.left && i.right > n.right).OrderBy(i => i.right - n.right).FirstOrDefault();
    if (parent != null)
        parent.AddChild(n);
}

但这是相当低效的。

有没有更好（这意味着更快）的方法？

编辑

可能的解决方案（如 Chris 建议的那样）：

var stack = new Stack<Node>(nodes.Take(1));
foreach (var n in nodes.Skip(1))
{
    while (stack.Peek().right < n.left)
        stack.Pop();

    stack.Peek().addChild(n);
    stack.Push(n);
}

节点必须按 排序left。

4

3 回答 3

3

我可能会考虑探索的方法是按左排序，然后你可以迭代一次。

当您到达左侧并将其粘贴在堆栈上时，您“打开”了一个节点。

当您到达要处理的新节点时，您可以通过确定其右侧是否小于新节点左侧来检查堆栈顶部的节点是否应该关闭。如果是，您将它从堆栈中移除（关闭它）并且您已经处理了它的所有子级。然后，您检查堆栈的新顶部，直到找到仍然打开的堆栈。然后将当前节点作为子节点添加到堆栈顶部的节点，然后打开该节点（因此它位于堆栈顶部）。

您链接的维基百科页面上的图表（http://en.wikipedia.org/wiki/Nested_set_model）是我对此的启发。

嵌套集图

我的算法基本上在中间行进，每当你进入其中一个集合时，我称之为打开，离开一个集合就是关闭。很明显，您最近打开但未关闭的集合将位于堆栈的顶部，因此您放置孩子的位置。

我认为由于排序的原因，它的复杂性应该是 O(nlogn)。其余的只是 O(n)。

于 2012-06-01T15:11:38.837 回答
0

我知道这个问题已经很老了（我没有找到关于该主题的任何其他问题/信息）而且我不知道“伪 C#”，但以防万一你们中的一些人对嵌套集合列表的递归算法感到困惑=>树算法，这是我来到的（在scala中）：

def retrieveUserFolderTree(user: User): Future[List[Folder]] = {
  // Get a list of user's folders orderred by left asc
  val dbFoldersPromise = folderDAO.findUserFolders(user)

  dbFoldersPromise.map {
    case rootFolder :: tail => generateChildren(0, rootFolder.right, tail)
    case Nil => Nil
  }
}

private def generateChildren(currentLeft: Int, currentRight: Int, dbFolders: Seq[DBFolder]): List[Folder] = {
  dbFolders match {
    case dbFolder :: tail if dbFolder.left > currentRight => Nil
    case dbFolder :: tail if dbFolder.left > currentLeft => Folder(dbFolder.id, dbFolder.name, generateChildren(dbFolder.left, dbFolder.right, tail)) :: generateChildren(dbFolder.right, currentRight, tail)
    case dbFolder :: tail => generateChildren(currentLeft, currentRight, tail)
    case Nil => Nil
  }
}

希望这会对某人有所帮助。

于 2014-10-27T21:20:40.830 回答
0

也许我在某个地方错过了一步，但是当我使用上面的逻辑处理这个问题时，我最终在堆栈上发现了几个重复的元素。它们按预期在树中，但另外它们也在根节点上方的堆栈顶部。我不得不在最后添加一个小循环来清理堆栈。

        var stack = new Stack<DvrNode>(nodes.Take(1));
        foreach (var n in nodes.Skip(1))
        {
            while (stack.Peek().Right < n.Left)
                stack.Pop();

            ((List<DvrNode>)stack.Peek().Children).Add(n);
            stack.Push(n);
        }

        while (stack.Peek().Left != 1)
            stack.Pop();
于 2016-05-03T15:41:52.337 回答