在树中选择节点及其父节点的算法

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)