Python非递归实现树节点删除并将子节点挂载到父节点的问题

我需要遍历任意结构的树并构建新树，要求删除指定节点时，将该节点的子节点直接挂载到其父节点上。实现过程不使用递归和类，仅使用列表、字典等基础数据结构。

以下代码可实现遍历原始树并尝试构建新树，暂未完成使用栈构建新树的逻辑：

original_tree = {
    'id': 1,
    'children': [
        {
            'id': 2,
            'children': [{'id': 3}, {'id': 4}]
        },
        {
            'id': 5,
            'children': [
                {'id': 6, 'children': [{'id': 7}]},
                {'id': 8, 'delete': True, 'children': [{'id': 9}, {'id': 10}]},
                {'id': 11}
            ]
        }
    ]
}

stack = [original_tree]
new_tree = {}

while len(stack):
    node = stack.pop(0)
    print(node['id'])
    children = node.get('children', [])

    # === Start building a new tree ===
    if not node.get('delete'):
        new_tree['id'] = node['id']
        pass
    # ================================

    for i in range(len(children) - 1, -1, -1): 
        stack.insert(0, children[i])

核心思路是栈中同时存储原节点、新树中的父节点对象，遍历过程中判断当前节点是否需要删除：

• 不需要删除：创建新节点挂载到父节点下，后续子节点的父节点改为当前新节点
• 需要删除：不创建新节点，后续子节点的父节点直接使用当前节点的父节点

original_tree = {
    'id': 1,
    'children': [
        {
            'id': 2,
            'children': [{'id': 3}, {'id': 4}]
        },
        {
            'id': 5,
            'children': [
                {'id': 6, 'children': [{'id': 7}]},
                {'id': 8, 'delete': True, 'children': [{'id': 9}, {'id': 10}]},
                {'id': 11}
            ]
        }
    ]
}

# 栈元素格式：(原节点, 新树父节点对象)
stack = [(original_tree, None)]
new_tree = None

while stack:
    node, parent = stack.pop(0)
    children = node.get('children', [])
    current_new_node = None

    # 处理当前节点
    if not node.get('delete'):
        current_new_node = {'id': node['id'], 'children': []}
        if parent is None:
            # 根节点
            new_tree = current_new_node
        else:
            # 挂载到父节点
            parent['children'].append(current_new_node)
    else:
        # 节点被删除，子节点直接挂到parent上，current_new_node用parent代替
        current_new_node = parent

    # 子节点倒序入栈保证遍历顺序不变，子节点的父节点设为current_new_node
    for i in range(len(children)-1, -1, -1):
        stack.insert(0, (children[i], current_new_node))

# 输出验证
import json
print(json.dumps(new_tree, indent=2, ensure_ascii=False))

运行输出结果 #

{
  "id": 1,
  "children": [
    {
      "id": 2,
      "children": [
        {
          "id": 3,
          "children": []
        },
        {
          "id": 4,
          "children": []
        }
      ]
    },
    {
      "id": 5,
      "children": [
        {
          "id": 6,
          "children": [
            {
              "id": 7,
              "children": []
            }
          ]
        },
        {
          "id": 9,
          "children": []
        },
        {
          "id": 10,
          "children": []
        },
        {
          "id": 11,
          "children": []
        }
      ]
    }
  ]
}

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