如何将非友好扁平化树表示转换为嵌套Python对象树结构

问题背景 #

给定一个扁平化表示的树结构，节点通过ID关联，且叶子节点单独存储在冗余列表中：

{
   "nodes":[
      {
         "id":0,
         "value":"and",
         "children":[
            1,
            4
         ]
      },
      {
         "id":1,
         "value":"or",
         "children":[
            2,
            3
         ]
      },
      {
         "id":4,
         "value":"or",
         "children":[
            5,
            6
         ]
      }
   ],
   "leafs":[
      {
         "id":2,
         "value":"some statement"
      },
      {
         "id":3,
         "value":"some statement"
      },
      {
         "id":5,
         "value":"some statement"
      },
      {
         "id":6,
         "value":"some statement"
      }
   ]
}

需要将其转换为嵌套结构，用Node和Leaf类实例替换ID引用，最终结构如下：

{
  "tree": {
    "id": 0,
    "value": "and",
    "children": [
      {
        "id": 1,
        "value": "or",
        "children": [
          {
            "id": 2,
            "value": "some statement"
          },
          {
            "id": 3,
            "value": "some statement"
          }
        ]
      },
      {
        "id": 4,
        "value": "or",
        "children": [
          {
            "id": 5,
            "value": "some statement"
          },
          {
            "id": 6,
            "value": "some statement"
          }
        ]
      }
    ]
  }
}

现有类定义存在参数和属性赋值错误，需先修正：

class Node:
    def __init__(self, id, operator):
        self.id = id
        self.value = operator
        self.children = []  # 初始化为空列表而非None，方便后续添加子节点

class Leaf:
    def __init__(self, id, value):
        self.id = id
        self.value = value  # 修正赋值逻辑，将传入的value赋值给实例属性

实现步骤 #

1. 构建ID-对象映射字典：遍历所有nodes和leafs，将每个节点的ID作为键，对应的Node或Leaf实例作为值存入字典，后续通过ID快速查找对象。
2. 定位根节点：找到ID为0的Node实例（即树的根节点）。
3. 递归替换子节点ID：遍历每个Node的children列表，将其中的ID替换为映射字典中对应的对象，若子对象是Node则继续递归处理其children。

完整代码实现 #

import json

class Node:
    def __init__(self, id, operator):
        self.id = id
        self.value = operator
        self.children = []

class Leaf:
    def __init__(self, id, value):
        self.id = id
        self.value = value

# 示例输入数据（可替换为从文件读取的JSON）
input_json = '''
{
   "nodes":[
      {
         "id":0,
         "value":"and",
         "children":[1,4]
      },
      {
         "id":1,
         "value":"or",
         "children":[2,3]
      },
      {
         "id":4,
         "value":"or",
         "children":[5,6]
      }
   ],
   "leafs":[
      {
         "id":2,
         "value":"some statement"
      },
      {
         "id":3,
         "value":"some statement"
      },
      {
         "id":5,
         "value":"some statement"
      },
      {
         "id":6,
         "value":"some statement"
      }
   ]
}
'''

def build_nested_tree(input_data):
    # 1. 构建ID到对象的映射
    id_map = {}
    
    # 处理非叶子节点
    for node_data in input_data['nodes']:
        node = Node(node_data['id'], node_data['value'])
        node.children = node_data['children']  # 先暂存ID列表
        id_map[node_data['id']] = node
    
    # 处理叶子节点
    for leaf_data in input_data['leafs']:
        leaf = Leaf(leaf_data['id'], leaf_data['value'])
        id_map[leaf_data['id']] = leaf
    
    # 2. 递归替换子节点ID为实际对象
    def replace_children(node):
        # 将children中的ID替换为对应对象
        new_children = []
        for child_id in node.children:
            child_obj = id_map[child_id]
            new_children.append(child_obj)
            # 如果子对象是Node，继续递归处理它的children
            if isinstance(child_obj, Node):
                replace_children(child_obj)
        node.children = new_children
    
    # 找到根节点（假设根节点ID为0）
    root_node = id_map[0]
    replace_children(root_node)
    
    return {"tree": root_node}

# 解析输入JSON
data = json.loads(input_json)
# 构建嵌套树
result = build_nested_tree(data)

# 验证结果（将对象转为JSON格式输出）
def obj_to_dict(obj):
    if isinstance(obj, Node):
        return {
            "id": obj.id,
            "value": obj.value,
            "children": [obj_to_dict(child) for child in obj.children]
        }
    elif isinstance(obj, Leaf):
        return {
            "id": obj.id,
            "value": obj.value
        }
    else:
        return obj

print(json.dumps(obj_to_dict(result), indent=2))

输出结果 #

运行上述代码后，将输出符合需求的嵌套结构JSON：

{
  "tree": {
    "id": 0,
    "value": "and",
    "children": [
      {
        "id": 1,
        "value": "or",
        "children": [
          {
            "id": 2,
            "value": "some statement"
          },
          {
            "id": 3,
            "value": "some statement"
          }
        ]
      },
      {
        "id": 4,
        "value": "or",
        "children": [
          {
            "id": 5,
            "value": "some statement"
          },
          {
            "id": 6,
            "value": "some statement"
          }
        ]
      }
    ]
  }
}

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