二叉樹“獲取打開列表”SQL查詢

我有一個看起來像這樣的節點表，而且它有一個inserted_at列：

id        |  parent_id
----------+-----------
1         |  nil
2         |  1
3         |  1
4         |  2
5         |  2
6         |  3
7         |  4
8         |  5
9         |  6
10        |  3

它是一個二叉樹的表示，如下所示：

            1
         /     \
       2         3
    /   \       /   \
   4    5      10    6
  /     /             \
 7     8               9

我正在嘗試編寫一個遞歸 SQL 查詢，該查詢獲取一個 nope 節點列表——在它們下面有 1 或 2 個開放位置的節點——即未列為其他節點 2 次的 parent_id 的節點列表。

這個“open_list”將包含 4,5,10,6,7,8,9，因為所有這些節點的子節點都少於兩個。那麼這在SQL中可能嗎？一個產生二叉樹“開放列表”的查詢。

也許我必須是一個使用 WITH 語句的遞歸 CTE 表，它本身有一個連接？

With recursive (
  select *
  join on self... recursive
)
select * from recursive

這就是我完全業餘的直覺所在。有更多經驗的人可以指導我回答嗎？

在這種情況下，我認為您不需要遞歸查詢，只需獲取那些沒有兩個子記錄的記錄。

select *
from   mytable
where  id not in(select   parent_id
                 from     mytable
                 group by parent_id
                 having   count(*) > 1);

編號 | parent_id
-: | --------:
 4 | 2
 5 | 2
 6 | 3
 7 | 4
 8 | 5
 9 | 6
10 | 3

dbfiddle在這裡

引用自：https://dba.stackexchange.com/questions/175384