从二叉树中删除一个节点及其所有子节点，而不使用树数据结构

Question

假设我有一个数组作为输入，比如

array = -1 0 0 1 2 1 3 5 5 6 6

（这实际上是二叉树的父数组表示）

在本例中，树如下所示：

         0
       /   \
      1     2
     / \   /
    3   5 4
   /   / \
  6   7   8
 / \
9  10

我还有另外一个建议，比如说

input = 1

（这是要从树中删除的节点）

我想实现的基本目标是：

1. 删除数组[输入]
2. 在剩余数组中搜索输入变量
3. 删除value=input的所有元素
4. 存储已删除值的索引
5. 在剩余的数组中搜索value=索引
6. 删除这些元素并存储它们的索引
7. 重复步骤5，直到不能删除更多内容

这是我想到的删除一个节点及其所有子节点的算法。在

因此，对于上面给出的样本输入，输出应该是：

-1 0 2

我选择不使用树数据结构，因为我觉得从父数组构造树，然后搜索节点并删除它可能会比较慢（虽然我可能错了）。在

我还没能在代码中实现这一点，我只有逻辑。每当我试图编写伪代码时，逻辑中的一个或多个问题就会变得明显。这就是为什么我还没有具体的代码发布在这里。所以我不知道要花多长时间。在

这是一个类赋值的问题，只使用树型数据结构就可以了，但是如果可能的话，我想在这种情况下实现一个更好的解决方案。在

感谢任何帮助。不需要给我完整的代码。只要有点提示就够了。在

Answer 1

这里是一个稍微修改过的算法版本的实现。在

不同的是，我们不是一个接一个地清除，而是一个接一个。这使用了这样一个事实：孩子们总是站在他们父母的右边，所以如果我们只浏览一次列表并在删除的过程中标记所有要删除的内容，我们就不会遗漏任何内容。在

这将使树处于非规范状态，因为删除的节点仍然存在，它们只是被标记为要删除（通过将其父节点设置为-2）。在

因此，我还添加了一个可选的压缩步骤，删除这些节点并对其余节点重新编号，以便剩余节点编号为0、1、2、。。。没有空隙。在

from itertools import islice, count

def delete_branch_from_tree(parents, branch_root,
                            compress=False, inplace=False):
    n = len(parents)
    if not inplace: # make a copy
        parents = parents[:]
    if branch_root == 0:
        parents[:] = [] if compress else n * [-2]
        return parents
    # -2 will indicate missing nodes
    parents[branch_root] = -2
    for node in range(branch_root+1, n):
        if parents[parents[node]] == -2:
            parents[node] = -2
    if compress: # remove nodes marked as missing, renumber the other ones
        c = count()
        new_number = [None if parent==-2 else next(c) for parent in parents]
        parents[:] = [new_number[parent] for parent in parents if parent != -2]
        # -1 was not in the lookup table (new_number), must fix manually
        parents[0] = -1
    return parents

演示：

^{pr2}$