python - Python 中的引用问题(树)

Question

我正在尝试删除所有仅包含零的子树。我的代码如下。现在，在根节点上运行removeFailures根本不会修改树(前后进行前序遍历会得到相同的结果)。

我认为这是因为当我说“root is None”时，我实际上并没有修改 root，我只是创建一个临时变量名称 root 可能吗？如果是这样的话我该如何解决这个问题？这个推理在 Java 中行不通吗？

    # Ex.
    #           4                      4
    #        /     \                /      \
    #       1       3              1        3
    #       / \    / \     -->    /       /  \
    #      0   0  4  6           0       4   6
    #     /\  /\                / \
    #    3 5 0  0              3  5


    class TreeNode:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right


    def removeFailures(root):
        if root is None:
            return True

        removeLeft = removeFailures(root.left)
        removeRight = removeFailures(root.right)
        if root.data == 0 and removeLeft and removeRight:
            root = None
            return True
        return False


    def preorder(root):
        print root.data
        if root.left:
            preorder(root.left)
        if root.right:
            preorder(root.right)

    example = TreeNode(4)
    example.left = TreeNode(1, TreeNode(0, TreeNode(3), TreeNode(5)), TreeNode(0, TreeNode(0), TreeNode(0)))
    example.right = TreeNode(3, TreeNode(4), TreeNode(6))
    preorder(example)
    print '*************************'

    removeFailures(example)

    preorder(example) #TODO

Answer 1

要检查树中的所有节点是否包含零，您必须循环遍历每个节点。一种可能性是创建一个 __iter__ 方法来查找树中的所有节点，然后可以应用 any 内置函数来确定它们是否都等于零。最后，一个简单的递归方法可以检查左右子节点，并在必要时删除。

为了简化创建树的过程，使用 kwargs 就地构建结构，而无需实现旋转方法或一长串赋值语句:

class Tree:
  def __init__(self, **kwargs):
    self.__dict__ = {i:kwargs.get(i) for i in ['left', 'right', 'val']}
  def __iter__(self):
    yield self.val
    yield from ([] if self.left is None else self.left)
    yield from ([] if self.right is None else self.right)
  @staticmethod
  def remove_empty_trees(_t):
    if not any(_t):
       return None
    _t.remove_trees()
    return _t
  def remove_trees(self):
    if not any([] if self.left is None else self.left):
       self.left = None
    else:
       self.left.remove_trees()
    if not any([] if self.right is None else self.right):
       self.right = None
    else:
       self.right.remove_trees()

<小时/>

#           4         
#        /     \    
#       1       3 
#       / \    / \  
#      0   0  4  6
#     /\  /\            
#    3 5 0  0
t = Tree(val=4, left=Tree(val=1, left=Tree(val=0, left=Tree(val=3), right=Tree(val=5)), right=Tree(val=0, left=Tree(val=0), right=Tree(val=0))), right=Tree(val=3, left=Tree(val=4), right=Tree(val=6)))
new_tree = Tree.remove_empty_trees(t)
print(print(new_tree.left.right))

输出:

None

为了处理整个树包含零节点的情况，staticmethod 提供了额外的检查。