我用一个父子表，并通过链表来表示子节点的顺序。这能得到正确的结果，但需要两个递归CTE步骤：第一步为每个子节点分配位置idx，第二步再按顺序分配嵌套层级。

是否可以把它们合并，使层级和位置idx在同一步中分配？我的尝试要么过早结束，要么分配的层级错误。

SQLite Fiddle

create table map (parent,child,prev,next);
insert into map values
(0,5,15,null),
(0,10,null,15),
(0,15,10,5),
(5,2,6,4),
(5,4,2,null),
(5,6,null,2),
(10,3,1,7),
(10,7,3,null),
(10,1,null,3),
(15,9,null,8),
(15,8,9,null),
(7,12,14,null),
(7,14,null,12),
(4,13,null,11),
(4,22,11,null),
(4,11,13,22);

with recursive
ordered_under_parent(parent,child,prev,next,idx) as
(
  select
    parent, child, prev, next, 1
  from
    map
  where
     prev is null
  UNION ALL
  select
     m.parent,m.child,m.prev,m.next,p.idx+1
  from
     map m join ordered_under_parent p
     on (m.parent,m.child)=(p.parent,p.next)
),
--select * from tree order by parent;
tree(child,level,idx) as
(
  VALUES(0,0,0)
  UNION ALL
  SELECT
     p.child, t.level+1, p.idx
  FROM
    ordered_under_parent p JOIN tree t ON p.parent=t.child
  ORDER BY
     2 DESC, p.idx asc
)
SELECT
   substr('..........',1,level*3) || child,
   level, idx
FROM tree;

解决方案

要在一次递归遍历中遍历整棵树，在递归部分使用两种不同的连接条件：

• t.child=r.next - 在同一层级连接相邻的节点（同级节点）。
• (t.parent=r.child and t.prev is null) - 连接下一层的第一个节点。

我假设需要 prev 与 next 两列来排列同一层级的节点（同级节点）。这种树结构通常用于在保持节点顺序的前提下，简化对节点或子树的插入或删除操作。查询的锚点是树的第0个节点（虚拟节点？）：

with recursive r as(
  select 0 rlvl
    ,0 tlvl
    ,0 root
    ,0 parent,0 child,0 prev,0 next
    ,concat('0','') path
    ,0 sib_idx
  union all
  select rlvl+1 rlvl
    ,case when t.child =r.next then tlvl else tlvl+1 end tlvl
    ,case when t.child =r.next then r.root else t.parent end root
    ,t.parent, t.child, t.prev, t.next
    ,concat(r.path,'(',case when t.child =r.next then r.sib_idx+1 else 1 end,')',t.child) path
    ,case when t.child =r.next then r.sib_idx+1 else 1 end sib_idx
  from r inner join map t
  on t.child =r.next
    or (t.parent=r.child and t.prev is null)
  where rlvl<40
)
select   parent, child, prev, next
  ,substr('..........',1,tlvl*3) || child figure
  ,rlvl, tlvl, root
  ,sib_idx
  , path
from r
order by path
;

输出：

rlvl - 递归层级
tlvl - 树层级
sib_idx - 同级索引
root - 下一层同级节点的根节点

max.recursion 对于16个节点且树层级为3时为9。同一层的同级节点逐步处理，子节点与下一层的首个节点同时处理。同一层级中同级节点的数量越多，递归循环的次数越多；而树的深度越深，递归次数越少。

Test example

起始节点 "5" 的输出：

with recursive r as(
  select 0 rlvl,0 tlvl,0 root
    ,parent,child,prev,next
    ,concat(child,'') path
    ,0 sib_idx
  from map t
  where child=5
  union all
  ...

从起始子节点为13开始时：