计算二叉树结构中的节点数

Question

给定一个特定的起始节点父 id ( pid) ，我需要计算二叉树结构中的左右节点（按 joinDate 分组的输出）。

树存储在下表中：

例如，使用pid = 4您将获得 2 cid(5 和 11 )，然后您将使用它们作为新的pid(5, 11)。当cid为 null 或已遍历完整树时，计算所有placement = Land placement = R。其他位置如“M”应该被忽略。

插图：

选定起始节点 4 的预期输出：

+-----------+-------------+-------+
| placement | joiningDate | Total |
+-----------+-------------+-------+
| L         | 2015-02-02  |     3 |
| R         | 2015-02-02  |     1 |
| L         | 2015-08-21  |     4 |
| L         | 2015-12-12  |     1 |
+-----------+-------------+-------+

Answer 1

这在 SQL Server 中使用递归公用表表达式最容易实现。

表定义

DECLARE @binaryUser AS TABLE
(
    id          integer NOT NULL,
    joiningDate date NOT NULL,
    placement   char(1) NOT NULL,
    pId         integer NOT NULL,
    cId         integer NOT NULL,
    referBy     integer NOT NULL
);

数据

INSERT @binaryUser
    (id, joiningDate, placement, pid, cid, referBy)
VALUES
    (4, '20150202', 'L', 4, 5, 4),
    (6, '20150202', 'R', 5, 8, 4),
    (8, '20150202', 'R', 4, 11, 4),
    (9, '20150202', 'L', 5, 10, 4),
    (25, '20151212', 'L', 8, 9, 4),
    (31, '20150821', 'R', 8, 12, 4),
    (33, '20150821', 'R', 12, 13, 4),
    (36, '20150821', 'R', 9, 14, 4),
    (37, '20150821', 'M', 9, 15, 4),
    (38, '20150821', 'L', 10, 16, 4),
    (39, '20150821', 'M', 4, 17, 4);

解决方案

这是作为脚本提供的，但将其转换为存储过程很简单。基本思想是递归遍历树，然后计算找到的行数。

DECLARE @pId integer = 4;

-- Recursive CTE
WITH R AS
(
    -- Anchor
    SELECT 
        BU.joiningDate,
        BU.cId,
        BU.placement
    FROM @binaryUser AS BU
    WHERE
        BU.pId = @pId
        AND BU.placement IN ('L', 'R')

    UNION ALL

    -- Recursive part
    SELECT
        BU.joiningDate,
        BU.cId,
        R.placement
    FROM R
    JOIN @binaryUser AS BU
        ON BU.pId = R.cId
    WHERE
        BU.placement IN ('L', 'R')
)
-- Final groups of nodes found
SELECT
    R.placement,
    R.joiningDate,
    Total = COUNT_BIG(*)
FROM R
GROUP BY
    R.placement,
    R.joiningDate
OPTION (MAXRECURSION 0);

SEDE Demo

输出：

???????????????????????????????????
? placement ? joiningDate ? Total ?
???????????????????????????????????
? L         ? 2015-02-02  ?     3 ?
? R         ? 2015-02-02  ?     1 ?
? L         ? 2015-08-21  ?     4 ?
? L         ? 2015-12-12  ?     1 ?
???????????????????????????????????