查找树的高度

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