如何替换 python 中的子树

Question

我的树数据结构如下：

class Node(object):
    def __init__(self, data):
        self.data       = data
        self.children   = []
    def add_child(self, obj):
        self.children.append(obj)

然后我创建了一个方法来完成它。

def replace(node, newNode):
    if node.data == 1:
        node = newNode
        return
    else:
        for i in xrange(0, len(node.children)):
            replace(node.children[i], newNode)

这个方法就是这样调用的：

replace(mytree,newNode)

由于是递归调用，我认为对象被销毁并且没有发生赋值。

我手动尝试过：

mytree.children[0].children[0] = newNode

然后树被正确更新。我怎样才能用我上面的方法实现它？

Answer 1

作业 node = newNode 不符合您的要求。它不会在任何地方用 newNode 替换您所知道的 node 对象。它只是重新绑定局部变量名称 node 以指向与另一个局部名称 newNode 相同的对象。对第一个节点的其他引用（例如在其父节点的 children 列表中）将保持不变。

真正做你想做的事需要更多的技巧。最好的方法通常是根本不替换节点，而是替换其内容。即，将 node.data 和 node.children 设置为等于 newNode.data 和 newNode.children，并保留 node。仅当存在对 node 或 newNode 的其他引用并且您希望它们在替换后正常工作时才无法正常工作。

另一种方法是在您要查找的节点的父节点中进行替换。这在树的顶部不起作用，因此您需要特殊的逻辑来处理这种情况。

def replace(node, newNode):
    if node.value == 1:
        raise ValueError("can't replace the current node this way")

    for index, child in enumerate(node.children):
        if child.data == 1:
            node.children[index] = newNode
            return True

        if replace(child, newNode):
            return True

    return False

我还添加了一些额外的逻辑来在找到合适的节点时停止树的递归处理。如果已进行替换，该函数将 return True，如果未找到正确的 data 值，则该函数将 False。

如何替换 python 中的子树

How to replace a subtree in python

python

tree