代码之家 › 专栏 › 技术社区 › Yuki.kuroshita

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

binary-tree tree python-2.7 arrays python

Yuki.kuroshita · 技术社区 · 7 年前

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

数组=-1 0 1 2 1 3 5 5 6 6

(这实际上是二叉树的父数组表示)

在本例中,树如下所示:

我还有另一个输入,比如

输入=1

(这是要从树中删除的节点)

我想要实现的基本目标是:

删除数组[输入]
在剩余数组中搜索输入变量
删除value=input的所有元素
存储已删除值的索引
在剩余数组中搜索value=索引
删除这些元素并存储其索引
重复步骤5,直到无法删除更多内容

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

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

-1 0 2

我选择不使用树数据结构,因为我觉得从父数组构建树,然后搜索节点并删除它可能会比较慢(尽管我可能错了)。

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

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

非常感谢您的帮助。不需要给我完整的代码。只要一些指针就足够了。

1 回复 | 直到 7 年前

Paul Panzer 7 年前

下面是对算法稍加修改的版本的实现。

不同之处在于,我们并不是一个级别接着一个级别进行清除,而是一次完成所有操作。这使用了这样一个事实,即孩子总是在他们父母的右边,因此,如果我们只需浏览一次列表,并标记要删除的所有内容,我们就不会遗漏任何内容。

这会使树处于非规范状态,因为被删除的节点仍然存在,它们只是被标记为要删除(通过将其父节点设置为 -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

演示:

>>> tree = [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]
>>> 
>>> delete_branch_from_tree(tree, 1)
[-1, -2, 0, -2, 2, -2, -2, -2, -2, -2, -2]
>>> delete_branch_from_tree(tree, 1, compress=True)
[-1, 0, 1]
>>> delete_branch_from_tree(tree, 5)
[-1, 0, 0, 1, 2, -2, 3, -2, -2, 6, 6]
>>> delete_branch_from_tree(tree, 5, compress=True)
[-1, 0, 0, 1, 2, 3, 5, 5]