算法在树中选择的节点和他们的父母

Question

假设你有一个树状结构如下：

 a   [Level 0] 
/| \ 
    b c d  [Level 1] 
/\ | 
e f g  [Level 2] 
    | /\ 
    h i j [Level 3] 

我已经在数据库中表示这个像这样：

node parent 
------------ 
a  null 
b  a 
c  a 
d  a 
[...] 
h  f 
i  g  

我喜欢写一个函数，给定一个级别，它会返回该级别的所有节点及其父母。

例如：

f(0) => { a } 
f(1) => { a, b, c, d } 
f(2) => { a, b, c, d, e, f, g } 

有什么想法？

Answer 1

这里我遍历层次，每个层次都添加到表中。

create table mytable (
    node varchar(80), 
    parent varchar(80), 
    constraint PK_mytable primary key nonclustered (node) 
) 

-- index for speed selecting on parent 
create index IDX_mytable_parent on mytable (parent, node) 

insert into mytable values ('a', null) 
insert into mytable values ('b', 'a') 
insert into mytable values ('c', 'a') 
insert into mytable values ('d', 'a') 
insert into mytable values ('e', 'b') 
insert into mytable values ('f', 'b') 
insert into mytable values ('g', 'd') 
insert into mytable values ('h', 'f') 
insert into mytable values ('i', 'g') 
insert into mytable values ('j', 'g') 

create function fn_level (@level int) returns @nodes table (Node varchar(80), TreeLevel int) 
as begin 
    declare @current int 
    set @current = 0 
    while @current <= @level begin 
     if (@current = 0) 
      insert @nodes (Node, TreeLevel) 
      select node, @current 
      from mytable 
      where parent is null 
     else 
      insert @nodes (Node, TreeLevel) 
      select mt.node, @current 
      from @nodes n 
       inner join mytable mt on mt.parent = n.Node 
      where n.TreeLevel = (@current - 1) 
     set @current = @current + 1 
    end 
    return 
end 

select * from fn_level(2) 

Answer 2

SQL并不总是很好地处理这些递归问题。

某些DBMS平台允许您使用Common Table Expressions这些有效的自定义查询，允许您通过数据结构递归。在MySQL中没有对此的支持，所以我建议你使用由另一种语言编写的脚本构造和管理的多个查询。

Answer 3

通常的方式做到这一点，除非你的SQL的味道都是有特殊非标功能，是构建具有这些列的路径表：

• parent_key
• child_key
• PATH_LENGTH

为了填补这个表，你使用递归或程序循环查找所有面值的ents，盛大父母，曾祖父母等等，为您的项目列表中的每个项目。递归或循环需要继续，直到找到返回新对的较长路径。 （a，b，1），（a，f，2），（a，h，3）等等。然后，为了得到所有在x级及以上级别的对象，你都会对所有的孩子做一个明确的选择，路径长度为< = x（与根结合，除非你在开始递归/递归时包含（null，root，0）循环。

这将是很好，如果SQL是更好的处理向图（树），但不幸的是，你有这样的额外的表来欺骗它。

Answer 4

用于MySQL的解决方案是不理想的。

假设树的最大深度被称为：

SELECT 
    nvl(e.node, nvl(d.node, nvl(c.node, nvl(b.node, a.node)))) item 
, nvl2(e.node, 5, nvl2(d.node, 4, nvl2(c.node, 3, nvl2(b.node, 2, 1)))) depth 
FROM table t AS a 
LEFT JOIN table t AS b ON (a.node = b.parent) 
LEFT JOIN table t AS c ON (b.node = c.parent) 
LEFT JOIN table t AS d ON (c.node = d.parent) 
LEFT JOIN table t AS e ON (d.node = e.parent) 
WHERE a.parent IS NULL 

这会给你的每一个节点，它的深度。之后，选择每个深度小于X的项目都是微不足道的。

如果树的深度未知，或者非常大，那么解决方案就像其他海报所说的那样迭代。

Answer 5

从杰森无耻地复制，我做了一个功能较少的解决方案，我用postgresql测试（它有函数 - 也许它会开箱即用）。

create table tree (
    node char(1), 
    parent char(1) 
); 

insert into tree values ('a', null); 
insert into tree values ('b', 'a'); 
insert into tree values ('c', 'a'); 
insert into tree values ('d', 'a'); 
insert into tree values ('e', 'b'); 
insert into tree values ('f', 'b'); 
insert into tree values ('g', 'd'); 
insert into tree values ('h', 'f'); 
insert into tree values ('i', 'g'); 
insert into tree values ('j', 'g'); 

ALTER TABLE tree ADD level int2; 
-- 
-- node parent level 
-- a - 1 
-- b a a.(level + 1) 
-- c a a.(level + 1) 
-- e b b.(level + 1) 
-- root is a: 
UPDATE tree SET level = 0 WHERE node = 'a'; 
-- every level else is parent + 1: 
UPDATE tree tout  -- outer 
    SET level = (
    SELECT ti.level + 1 
    FROM tree ti -- inner 
    WHERE tout.parent = ti.node 
    AND ti.level IS NOT NULL) 
    WHERE tout.level IS NULL; 

更新语句是纯sql，必须重复每个级别的填充表。

kram=# select * from tree; 
node | parent | level 
------+--------+------- 
a |  |  1 
b | a  |  2 
c | a  |  2 
d | a  |  2 
e | b  |  3 
f | b  |  3 
g | d  |  3 
h | f  |  4 
i | g  |  4 
j | g  |  4 
(10 Zeilen) 

我从'level = 1'开始，而不是'0'，因此，差异。

Answer 6

我对数据库或他们的术语知之甚少，但是如果您为了查找N级的所有元素而自己执行N次表的联合乘积，它会起作用吗？

换句话说，执行一个查询，在其中搜索具有父级A的所有条目。这将返回给您所有子级的列表。然后，重复查询以查找每个这些孩子的孩子。重复此过程直到找到N级的所有孩子。

以这种方式，您不必预先计算每个项目的深度。