홈>2020-02-25 23:30

pointers - 파이썬에서 참조가 문제 (나무)

0 만 포함하는 모든 하위 트리를 제거하려고합니다. 내 코드는 다음과 같습니다. 지금, 루트 노드에 removeFailures를 실행하는 것은 전혀 트리를 수정하지 않습니다 (전순 통과하기 전에 일을하고 이후에 같은 결과를 제공합니다).

나는 "root is None"이라고 말할 때 실제로 root를 수정하지 않고, 아마도 temp 변수 이름을 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

pythonpointersreferencetree

답변 # 1

트리의 모든 노드에 0이 포함되어 있는지 확인하려면 각 노드를 반복해야합니다. 가능성은 __iter__ 를 만드는 것입니다 트리의 모든 노드를 찾은 다음 any 를 찾는 방법 내장 함수를 적용하여 모두 0인지 확인합니다. 마지막으로 간단한 재귀 방법으로 왼쪽 및 오른쪽 자식을 확인하고 필요한 경우 제거 할 수 있습니다.

트리를 간단하게 만들려면 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

전체 트리가 0의 노드를 포함하는 경우를 처리하기 위해 staticmethod 추가 점검을 제공합니다.

답변 # 2

재귀 적으로 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 로 설정해야합니다. 제대로 그것을 제거 할 수 있습니다.

Python2.net

pointers - 파이썬에서 참조가 문제 (나무)

관련 자료