Algorithm for selecting nodes and their parents in a tree

Question

Let's say you have a tree structure like this:

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

I presented this in the database as follows:

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

I would like to write a function that, given the level, will return all the nodes of this level and their parents.

For instance:

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

Any thoughts?

Answer 1

Here I repeat the levels, adding them to the table with the level at which it is located.

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

The usual way to do this, unless your taste of SQL has a special custom function for it, is to create a path table containing these columns:

• parent_key
• child_key
• PATH_LENGTH

, , , , .. . , , .

, , (a, b, 1), (a, f, 2), (a, h, 3) .. , x , path_length <= x ( , (null, root, 0), /.

, SQL (), , , .

Answer 3

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

node . X.

, , .

Answer 4

, , 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" a, .

Answer 5

SQL .

, , , . MySQL , , script, .

Answer 6

, , N , N?

In other words, run a query in which you search for all records with parent A. This will return you a list of all its children. Then repeat the query to find the children of each of these children. Repeat this procedure until you find all the children at level N.

Thus, you do not need to pre-calculate the depth of each element.