Беда со ссылками в 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

После рекурсивного вызова removeFailures() на дочерних узлах необходимо установить их на None, если они были успешно удалены:

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

    removeLeft = removeFailures(root.left)
    removeRight = removeFailures(root.right)

    # Check if successfully removed children
    if removeLeft:
        root.left = None
    if removeRight:
        root.right = None

    if root.data == 0 and removeLeft and removeRight:
        root = None
        return True
    return False

Вывод:

4
1
0
3
5
0
0
0
3
4
6
*************************
4
1
0
3
5
3
4
6

Установка самого узла на None недостаточно, поскольку родительский узел все еще содержит ссылку на него.Следовательно, для правильного удаления необходимо установить все ссылки на этот узел на None.

Answer 2

Чтобы проверить, что все узлы в дереве содержат ноль, вам придется зацикливаться на каждом из этих узлов.Можно создать метод __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обеспечивает дополнительную проверку.