查找樹的高度

Question

使用SQL，我想跟隨樹結構直到最後一頁。樹= 1和結= 2;樹= 1和結= 3;樹= 1和結=空（累積概率）;樹= 2和結4 =樹= 2和結= 5;樹= 2和結是空（累積概率）;樹= 3和結= 6;樹= 3和結是空（累積概率）;樹= 4和結是空（累積概率）;樹= 5並且結是空（累積概率）;樹= 6並且結是空（累積概率）;

Answer 1

如果組織這樣的數據，你可以做以下

with TREETAB as (
select '1' treenode, '2' nodeval from dual 
union all 
select '1' treenode, '3' nodeval from dual 
union all 
select '1' treenode, 'leaf1' nodeval from dual 
union all 
select '2' treenode, '4' nodeval from dual 
union all 
select '2' treenode, '5' nodeval from dual 
union all 
select '2' treenode, 'leaf2' nodeval from dual 
union all 
select '3' treenode, '4' nodeval from dual 
union all 
select '3' treenode, 'leaf3' nodeval from dual 
union all 
select '4' treenode, 'leaf4' nodeval from dual 
union all 
select '5' treenode, 'leaf5' nodeval from dual 
union all 
select '6' treenode, 'leaf6' nodeval from dual 
) 

select * 
    from (SELECT t.*, CONNECT_BY_ISLEAF Leaf, 
       SYS_CONNECT_BY_PATH(nodeval, '/') "Path", level 
      FROM TREETAB t 
      start with t.treenode = 1 
     CONNECT BY PRIOR t.nodeval = to_char(t.treenode)) 
where Leaf = 1 
order by treenode; 

如果不需要對樹，葉和路徑的詳細信息，你可以只檢查什麼也沒有同等價值treenode爲nodeval這樣

with TREETAB as 
(select '1' treenode, '2' nodeval 
    from dual 
    union all 
    select '1' treenode, '3' nodeval 
    from dual 
    union all 
    select '1' treenode, 'leaf1' nodeval 
    from dual 
    union all 
    select '2' treenode, '4' nodeval 
    from dual 
    union all 
    select '2' treenode, '5' nodeval 
    from dual 
    union all 
    select '2' treenode, 'leaf2' nodeval 
    from dual 
    union all 
    select '3' treenode, '4' nodeval 
    from dual 
    union all 
    select '3' treenode, 'leaf3' nodeval 
    from dual 
    union all 
    select '4' treenode, 'leaf4' nodeval 
    from dual 
    union all 
    select '5' treenode, 'leaf5' nodeval 
    from dual 
    union all 
    select '6' treenode, 'leaf6' nodeval from dual) 

select * 
    from TREETAB t 
where not exists 
(select t.treenode from TREETAB t2 where t2.treenode = t.nodeval) 

Answer 2

假設你正在談論的概率是相等的概率爲每個分支則：

WITH data (tree, knot) AS (
    SELECT 1, 2 FROM DUAL UNION ALL 
    SELECT 1, 3 FROM DUAL UNION ALL 
    SELECT 1, NULL FROM DUAL UNION ALL 
    SELECT 2, 4 FROM DUAL UNION ALL 
    SELECT 2, 5 FROM DUAL UNION ALL 
    SELECT 2, NULL FROM DUAL UNION ALL 
    SELECT 3, 6 FROM DUAL UNION ALL 
    SELECT 3, NULL FROM DUAL UNION ALL 
    SELECT 4, NULL FROM DUAL UNION ALL 
    SELECT 5, NULL FROM DUAL UNION ALL 
    SELECT 6, NULL FROM DUAL 
), 
probabilities (tree, knot, probability) AS (
    SELECT tree, knot, 1/COUNT(1) OVER (PARTITION BY tree) FROM data 
), 
cumulative_probabilities (tree, knot, probability, path) AS (
    SELECT p.*, '/' || tree 
    FROM probabilities p 
    WHERE tree = 1 
UNION ALL 
    SELECT p.tree, p.knot, p.probability * cp.probability, cp.path || '/' || p.tree 
    FROM probabilities p 
     INNER JOIN 
     cumulative_probabilities cp 
     ON (p.tree = cp.knot) 
) 
SELECT * 
FROM cumulative_Probabilities 
WHERE knot IS NULL; 

輸出：

TREE KNOT PROBABILITY PATH 
---- ---- ----------- ------ 
    1  0.333333333 /1 
    3  0.166666667 /1/3 
    2  0.111111111 /1/2 
    6  0.166666667 /1/3/6 
    4  0.111111111 /1/2/4 
    5  0.111111111 /1/2/5