如何从树的任意父节点获取所有叶节点

Question

如何从树的任意父节点获取所有叶节点

3

我正在开发一个使用Sqlite的Android应用程序，我有一个树形结构，我在数据库中表示如下：

        +------+------+-------+------+
        |comp_id nodeId parent| text |
        |------|------|-------|------|
        |  146 |  1   |  -1   | Top  |
        |      |      |       |      |
        | 146  |  2   |  1    | Ch1  |
        |      |      |       |      |
        | 146  |  3   |  2    | Leaf |
        |      |      |       |      |
        |  ... |      |       |      |
        | 152  |  1   |  -1   | Top  |
        +------+------+-------+------+

我在编写一个算法时遇到了困难，希望能够以下面这种自包含的方法来返回任意节点下的所有叶子节点。

Node
{
   public Node[] getAllLeafs()
   {
      // traverse all the way down the tree
      // and get only leafs
   }
}

如果通过修改我的表结构和/或使用SQL能够更轻松地完成此操作，请在翻译中提到，因为我能够这样做。

- sprocket12

你有两个具有相同“nodeId”的节点。comp_id的意思是什么？展示一个期望输出的例子！ - CL.

@CL。comp_id 意味着编译 ID，就像一本书，节点是章节名称（可能有子章节），而叶子节点就像页面或段落。这是我能给出的最接近的例子。 - sprocket12

5个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Boris Pavlović · Answer 1

选择所有的行，它们的node_id不是其他行的父级，即它们是叶节点。

select *
from   tree_table
where  node_id not in (
   select distinct parent from tree_table
);

- Warlord · Answer 2

你可以编写一个递归方法，返回其子节点中所有叶子节点的数组，如果一个节点有子节点，则返回该节点本身，如果没有子节点，则该节点本身就是叶子节点。

public Node[] getAllLeafs() {

    ArrayList<Node> allLeafs = new ArrayList<Node>();

    if (getAllChildren().size() == 0) {
        allLeafs.add(this);
        return (Node[]) allLeafs.toArray();
    } else {
        for (Node child : this.getAllChildren()) {
            allLeafs.addAll(child.getAllLeafs());
        }
    }
}

这样你就可以在一个方法中保持逻辑，而不必冗余地遍历不重要的节点。结构方法的实现取决于您。

- Bhoot · Answer 3

我认为这个逻辑会起作用：

select node_id
from tree_table where node_id not in 
(select a.node_id 
from tree_table as a, tree_table as b
where a.node_id = b.parent);

内部查询找出那些在同一表中还是父节点的节点。外部查询找出那些不是任何节点的父节点，因此必须是叶节点。希望这可以帮助！

- Martin Podval · Answer 4

那么，获取所有子节点而不是直接节点的原因是什么呢？第二个选项显然更简单。

我认为没有一个合理的解决方案，也许图数据库可以。关键在于你可以选择：

为了使每个节点都能够持久化所有父ID（直接和非直接的），您可以设计一个新表，其中包含外键。但是这种解决方案似乎过于繁重。而且这样的表应该会呈指数级增长。
获取整个树的方法是将其一起获取。这是我们在进行了四年的数据库研究后使用的方法。由于缓冲和读取硬盘博客的原因，DB被设计为获取相邻数据。您可以通过使用正确的索引等来改进此解决方案。我的意思是，有时从DB中获取连续的驱动器段比制作复杂的查询，然后在Java代码中搜索所有节点更好。

请注意，通过根索引ID获取整个树只需要进行一次DB读取。另一方面，通常使用嵌套查询或使用连接的选择使用更多的读取，需要匹配ID，可能需要临时表等。（索引处理，锁定等）

您应该肯定使用各种NoSQL DB，但也要使用RDBMS。

- CL. · Answer 5

使用SQLite 3.8.3或更高版本，您可以使用以下查询来计算从特定节点开始的子树，然后获取该子树中的叶子节点：

WITH RECURSIVE subtree(comp_id, nodeId, parent, text)
AS (SELECT *
    FROM MyTable
    WHERE comp_id = 146 AND nodeId = 1  -- start node
    UNION ALL
    SELECT MyTable.*
    FROM MyTable
    JOIN subtree ON MyTable.comp_id = subtree.comp_id
                AND MyTable.parent  = subtree.nodeid)
SELECT *
FROM subtree
WHERE nodeid NOT IN (SELECT parent
                     FROM subtree)

在早期的SQLite版本中，您需要手动检索每个级别的节点。