Binary Tree(python)

09 Dec 2020 in Data Structure on 자료구조, 이진 트리, Python, 재귀

이진 트리의 구현(깊이 우선 순회 알고리즘)

# 이진 트리는 노드로 구성
# 깊이 우선 순회 알고리즘을 적용하여 재귀를 활용
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l, r) + 1

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder
        if self.right:
            traversal += self.right.preorder
        return traversal

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal += self.data
        return traversal

class BinaryTree:
    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

    # 이진 트리의 중위 순회
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

    # 이진 트리의 전위 순회
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

    # 이진 트리의 후위 순회
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

오류난 부분

• Node 클래스의 size() 메소드에서 종료 조건에서의 값이 0이 주어져서 return 값이 0이 되는게 아닌가하는 생각이 들었지만 기존의 root를 더해줌으로써 의문이 풀렸다. 그리고 self.left, self.right 모두 노드라는 것이 중요했다.