Codeigniter二叉树(MLM)1:2架构父级层级插入逻辑咨询

算力阿峰

2026-5-25

二叉树节点层级升级逻辑实现方案

核心思路

这个需求的本质是从下往上递归验证节点的"完全二叉链"深度：每个节点的层级等于它往下连续满足「每个子节点都有2个子节点」的最大层数。举个例子：

自身有2个子节点，但子节点没有子节点 → 层级1
自身有2个子节点，且每个子节点都有2个子节点 → 层级2
以此类推，每多一层满足条件的子节点链，层级就加1

具体步骤

1. 初始化节点基础状态

先给每个节点计算两个关键值：

has_two_children：标记该节点是否恰好有2个子节点（是=1，否=0）
max_valid_depth：初始值等于has_two_children，代表当前节点能满足的最低层级条件

2. 从叶子节点往上迭代更新

因为父节点的层级依赖子节点的状态，必须从最底层的节点开始，逐层向上刷新：

对于每个父节点，如果它的两个子节点的max_valid_depth完全相等，说明这一层的子节点都满足了相同层级的条件，父节点的max_valid_depth可以升级为「子节点深度+1」
重复这个迭代过程，直到没有节点的max_valid_depth再发生变化为止

3. 映射最终层级

节点的最终层级就是它的max_valid_depth值（如果max_valid_depth为0，说明不满足任何层级条件，无需插入到层级表中）

示例实现（SQL版本）

假设你的member_relation表结构如下：

CREATE TABLE member_relation (
    id INT PRIMARY KEY,
    parent_id INT,
    level INT DEFAULT 0 -- 存储最终计算的层级
);

步骤1：计算节点子节点数量与初始标记

先创建临时表存储中间计算结果：

CREATE TEMP TABLE node_stats AS
SELECT
    id,
    parent_id,
    (SELECT COUNT(*) FROM member_relation child WHERE child.parent_id = main.id) = 2 AS has_two_children,
    CASE WHEN (SELECT COUNT(*) FROM member_relation child WHERE child.parent_id = main.id) = 2 THEN 1 ELSE 0 END AS max_valid_depth
FROM member_relation main;

步骤2：迭代更新深度值

用循环实现逐层向上刷新：

DECLARE updated_count INT DEFAULT 1;

WHILE updated_count > 0 DO
    -- 当两个子节点的深度相同时，升级父节点的深度
    UPDATE node_stats parent
    SET max_valid_depth = parent.max_valid_depth + 1
    WHERE EXISTS (
        SELECT 1
        FROM node_stats child1
        JOIN node_stats child2 ON child1.parent_id = parent.id AND child2.parent_id = parent.id AND child1.id != child2.id
        WHERE child1.max_valid_depth = parent.max_valid_depth
          AND child2.max_valid_depth = parent.max_valid_depth
    );

    -- 统计更新行数，无更新则退出循环
    GET DIAGNOSTICS updated_count = ROW_COUNT;
END WHILE;

步骤3：同步结果到原表

UPDATE member_relation main
SET level = (SELECT max_valid_depth FROM node_stats WHERE id = main.id)
WHERE EXISTS (SELECT 1 FROM node_stats WHERE id = main.id AND max_valid_depth > 0);

示例实现（Python版本）

如果用代码逻辑处理，可以用字典存储节点信息，从叶子节点往上遍历：

# 假设已从数据库获取所有节点，格式为列表：每个元素是{"id": xxx, "parent_id": xxx}
nodes = [...]

# 1. 构建节点映射与子节点列表
node_map = {node["id"]: node for node in nodes}
children_map = {node["id"]: [] for node in nodes}
for node in nodes:
    if node["parent_id"] is not None and node["parent_id"] in children_map:
        children_map[node["parent_id"]].append(node["id"])

# 2. 初始化每个节点的深度值
for node_id in node_map:
    node_map[node_id]["max_valid_depth"] = 1 if len(children_map[node_id]) == 2 else 0

# 3. 迭代升级深度
updated = True
while updated:
    updated = False
    # 遍历所有有子节点的父节点
    for parent_id in children_map:
        children = children_map[parent_id]
        if len(children) != 2:
            continue
        child1_depth = node_map[children[0]]["max_valid_depth"]
        child2_depth = node_map[children[1]]["max_valid_depth"]
        # 两个子节点深度相同，且父节点可升级时更新
        if child1_depth == child2_depth and node_map[parent_id]["max_valid_depth"] == child1_depth:
            node_map[parent_id]["max_valid_depth"] += 1
            updated = True

# 4. 提取满足条件的节点层级
level_nodes = {node["id"]: node["max_valid_depth"] for node in node_map.values() if node["max_valid_depth"] > 0}

注意事项

要处理循环引用和非二叉树节点（子节点数量不是0或2的情况），这类节点的max_valid_depth保持为0，不会被计入层级表
SQL实现时注意不同数据库的循环语法差异（比如MySQL用WHILE，PostgreSQL用LOOP）
超大规模树可以用递归CTE优化性能，但迭代方式更直观，便于调试

内容的提问来源于stack exchange，提问作者Prabu Deva