Python实现：基于branch_id构建多分支树状（森林）结构求助

针对原递归代码无法处理相同child ID但不同branch_id节点的问题，我们可以通过按分支分组、独立构建每棵树的方式生成森林结构，同时完整保留节点的所有额外属性。

核心思路 #

1. 按branch_id对节点进行分组，确保不同分支的节点完全隔离，避免ID冲突
2. 对每个分支内的节点，构建child ID -> 节点对象的映射，方便快速查找父/子节点
3. 为每个节点初始化children列表，用于存储嵌套结构
4. 找到每个分支的根节点（根据实际场景定义，比如parent为None），构建树结构
5. 将所有分支的树收集为最终的森林

实现代码 #

def build_forest(nodes):
    # 按branch_id分组存储节点
    branch_groups = {}
    for node in nodes:
        bid = node["branch_id"]
        if bid not in branch_groups:
            branch_groups[bid] = []
        branch_groups[bid].append(node)
    
    forest = []
    for branch_nodes in branch_groups.values():
        # 构建节点映射：child ID 指向节点副本（避免修改原数据）
        node_map = {n["child"]: n.copy() for n in branch_nodes}
        # 为每个节点初始化children列表
        for n_id in node_map:
            node_map[n_id]["children"] = []
        
        root_nodes = []
        for node in branch_nodes:
            parent_id = node["parent"]
            current_node = node_map[node["child"]]
            if parent_id is None:  # 此处可根据实际根节点规则调整（比如parent=0）
                root_nodes.append(current_node)
            else:
                # 将当前节点添加到父节点的children中
                if parent_id in node_map:
                    node_map[parent_id]["children"].append(current_node)
        
        # 将当前分支的所有根节点加入森林
        forest.extend(root_nodes)
    
    return forest

测试示例 #

# 测试用节点数据（包含相同child ID的跨分支节点）
test_nodes = [
    {"child": 1, "parent": None, "branch_id": "A", "name": "Root A", "type": "root"},
    {"child": 2, "parent": 1, "branch_id": "A", "name": "Child A1", "type": "leaf"},
    {"child": 3, "parent": None, "branch_id": "B", "name": "Root B", "type": "root"},
    {"child": 2, "parent": 3, "branch_id": "B", "name": "Child B1", "type": "node"},
    {"child": 4, "parent": 2, "branch_id": "B", "name": "Grandchild B1", "type": "leaf"}
]

# 生成森林
result_forest = build_forest(test_nodes)

# 格式化输出查看结果
import json
print(json.dumps(result_forest, indent=2))

输出结果 #

[
  {
    "child": 1,
    "parent": null,
    "branch_id": "A",
    "name": "Root A",
    "type": "root",
    "children": [
      {
        "child": 2,
        "parent": 1,
        "branch_id": "A",
        "name": "Child A1",
        "type": "leaf",
        "children": []
      }
    ]
  },
  {
    "child": 3,
    "parent": null,
    "branch_id": "B",
    "name": "Root B",
    "type": "root",
    "children": [
      {
        "child": 2,
        "parent": 3,
        "branch_id": "B",
        "name": "Child B1",
        "type": "node",
        "children": [
          {
            "child": 4,
            "parent": 2,
            "branch_id": "B",
            "name": "Grandchild B1",
            "type": "leaf",
            "children": []
          }
        ]
      }
    ]
  }
]

关键说明 #

• 分支隔离：通过branch_groups确保不同分支的节点完全独立处理，相同child ID不会互相干扰
• 属性保留：使用node.copy()复制原节点，所有额外属性（如name、type）都会被保留
• 灵活适配：根节点判断逻辑可根据实际业务调整（比如parent为0或空字符串）
• 兼容多根：单个分支内如果存在多个根节点（无父节点的节点），会被全部收集到森林中

内容的提问来源于stack exchange，提问作者Francesco Bosso