树。删除节点，但将其子节点传递给父节点

Question

我试图遍历任意一棵树并构建一棵新树，这将删除某些节点，但将它们的子节点连接到父节点。我不想使用递归或类，只使用列表、字典等

下面是完成一半工作的代码 - 它遍历原始树并尝试构建一棵新树，但我无法全神贯注地使用堆栈构建一棵新树。

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])

Answer 1

使用堆栈，您失去了父项和子项之间的 link — 无法知道您从堆栈中弹出的下一项是兄弟项还是父项。您可以通过在将项目添加到堆栈时跟踪父级来解决此问题。然后，当您从堆栈中弹出一个项目时，您将获得对父节点的引用。

要处理删除，您只需将已删除的子项添加到具有正确父项引用的堆栈中。这是一个简单的例子：

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 = [{'parent': None, 'node':original_tree}]
root = None

while len(stack):
    frame = stack.pop()

    node = frame['node']
    parent = frame['parent']
    
    # Allocate a new node
    new_node = {'id': node['id']}
    
    # Append the node to the parent if there is one; there won't be one for the root
    if parent is not None:
        if not node.get('delete'):
            parent.setdefault('children',[]).append(new_node)
    else:
        root = new_node
        
    children = node.get('children', [])

    print(node['id'])

    for child in reversed(children): 
        if child.get('delete'):
            # to delete a child, you need to add its children to the stack
            grand_children = child.get('children', [])
            for grand_child in reversed(grand_children):
                stack.append({'parent': new_node, 'node':grand_child})
        else:
            stack.append({'parent': new_node, 'node':child})

打印新树 root 得到：

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

已删除节点 8 的子节点现在是 5 的子节点。

（另外，对于 python 列表，在末尾弹出和附加更有效：pop() & append() 而不是 insert(0) 和 pop(0))

树。删除节点，但将其子节点传递给父节点

Tree. Delete node, but pass its children to a parent node

python

algorithm

tree

dictionary

loops