算法在樹中選擇的節點和他們的父母

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級的所有孩子。

以這種方式，您不必預先計算每個項目的深度。