在邻接表中查找子节点的根节点

Question

在一个邻接表中，给定一个节点的id，我该如何找到它对应的根节点？

注：

该表包含多个树，因此我不能简单地搜索null parentId。

更多信息：

这是我目前拥有的，是否存在任何问题或改进？

with tree as
(
    select 
        t.*

    from table1 t
    where t.id = @id

    union all 

    select 
        t2.*

    from tree
    join table1 t2 on tree.parentId = t2.id
) 

select * 
from tree
where parentId is null

- Brett Postin

Answer 1

我认为提供的任何解决方案都不如我自己的好，所以最终选择了这个：

with tree as
(
    select 
        t.*

    from table1 t
    where t.id = @id

    union all 

    select 
        t2.*

    from tree
    join table1 t2 on tree.parentId = t2.id
) 

select * 
from tree
where parentId is null

- Brett Postin

Answer 2

这个解决方案对我来说效果很好。虽然不能确定它的性能是否比你的更快。

declare @base_id as int;
set @base_id = 1;
WITH n(id) AS 
   (SELECT id 
    FROM table
    WHERE id = @base_id
        UNION ALL
    SELECT nplus1.ID
    FROM table as nplus1, n
    WHERE n.id = nplus1.ParentID)
SELECT id FROM n

(答案修改自ORACLE中CONNECT BY PRIOR在SQL SERVER中的模拟)

- NSjonas

---

谢谢您的回复。但是我不确定它是否回答了我的问题。除非我做错了什么，否则它似乎返回子树中每个节点的ID。 - Brett Postin

哦，对不起。我误读了问题...等我有空的时候，我会看看能否重新修改我的答案。 - NSjonas

Answer 3

这里是使用WHILE循环的代码。适用于表中的多个树:

declare @current_node int
declare @parent_node int
declare @MAX_ITERATIONS int
declare @count int

SET @current_node=@id -- node to start with
SET @MAX_ITERATIONS = 100 --maximum iterations count
SET @count=0 


while(@count<@MAX_ITERATIONS) -- to prevent endless loop  
begin
 select @parent_node=parentid from tree where id=@current_node
 if @parent_node is null -- root is found
  begin 
    break; 
  end
 set @current_node=@parent_node 
 SET @count=@count+1
end

if (@count=@MAX_ITERATIONS) SET @current_node=NULL --if it was endless loop

select @current_node; -- output root id

- valex