[python] 이진 탐색 트리 (binary Search tree) - 3. 순회

📗 이진 트리 (binary Search tree) - 순회

트리 순회

트리 순회는 트리에 저장된 값을 모두 확인할 때 사용한다. 순회 방법에 따라 값을 확인하는 순서가 다르다.순회의 종류로는 전위 순회 (preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)이 있다.

 

🔵 전위 순회 (preorder traversal)

💨 완성되어 있는 트리를 다른 서버에 리스트 형태로 보내서 그 서버에서 다시 트리를 구성할 때 사용

 노드 > 왼쪽 서브트리 > 오른쪽 서브트리 순으로 순회한다. 구현 방법은 다음과 같다.

• 노드 방문
• 왼쪽 서브트리 방문
• 오른쪽 서브트리 방문

전위 순회

전위 순회 결과:  F, B, A, D, C, E, G, I, H 

    def preorder_traverse(self):
        if self.head is not None:
            self.__preorder(self.head)

    def __preorder(self, cur):
        self.preorder_list.append(cur.val)
        print(cur.val)
        if cur.left is not None:
            self.__preorder(cur.left)
        if cur.right is not None:
            self.__preorder(cur.right)
            
            

🔵 중위 순회 (inorder traversal)

💨 오름차순 정렬할 때, O(n)의 시간 복잡도로 정렬 가능

왼쪽 서브트리 > 노드 > 오른쪽 서브트리 순으로 순회한다. 구현 방법은 다음과 같다.

• 왼쪽 서브트리 방문
• 노드 방문
• 오른쪽 서브트리 방문

중위 순회

중위 순회 결과:  A, B, C, D, E, F, G, H, I 

    def inorder_traverse(self):
        if self.head is not None:
            self.__inorder(self.head)

    def __inorder(self, cur):
        if cur.left is not None:
            self.__inorder(cur.left)

        self.inorder_list.append(cur.val)
        print(cur.val)

        if cur.right is not None:
            self.__inorder(cur.right)
            
            

🔵 후위 순회(postorder traversal)

왼쪽 서브트리 > 오른쪽 서브트리 > 노드 순으로 순회한다. 구현 방법은 다음과 같다.

• 왼쪽 서브트리 방문
• 오른쪽 서브트리 방문
• 노드 방문

 

후위 순회 결과:  A, C, E, D, B, H, I, G, F 

    def postorder_traverse(self):
        if self.head is not None:
            self.__postorder(self.head)

    def __postorder(self, cur):
        if cur.left is not None:
            self.__postorder(cur.left)

        if cur.right is not None:
            self.__postorder(cur.right)

        self.postorder_list.append(cur.val)
        print(cur.val)
        
        

---

🔵 전체 코드

# 노드 만들기
#         A(val)
#        /      \
#   B(left)     C(right)
class Node:
    def __init__(self, item):
        self.val = item
        self.left = None
        self.right = None


# 이진트리 만들기
class BinaryTree:
    # 초기값 head는 None
    def __init__(self):
        self.head = Node(None)

        self.preorder_list=[]
        self.inorder_list=[]
        self.postorder_list=[]

    # 값 추가하기 head가 없을 경우
    def add(self, item):
        if self.head.val is None:
            self.head.val = item

        # head가 있으면 왼쪽배치 or 오른쪽배치
        else:
            self.__add_node(self.head, item)

    # head가 있는 경우
    def __add_node(self, cur, item):
        print('부모:', cur.val, '자식:', item)
        # head 값이 크면 왼쪽으로
        if cur.val >= item:
            if cur.left is not None:
                self.__add_node(cur.left, item)
            else:
                cur.left = Node(item)
        # head 값이 작으면 오른쪽으로
        else:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)

    # 찾기!!
    def search(self, item):
        if self.head.val is None:
            return False
        else:
            return self.__search_node(self.head, item)

    def __search_node(self, cur, item):
        print(cur.val, item)
        if cur.val == item:
            return True
        else:
            if cur.val >= item:
                if cur.left is not None:
                    return self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    return self.__search_node(cur.right, item)
                else:
                    return False

    # 전위순회
    def preorder_traverse(self):
        if self.head is not None:
            self.__preorder(self.head)

    def __preorder(self, cur):
        self.preorder_list.append(cur.val)
        print(cur.val)
        if cur.left is not None:
            self.__preorder(cur.left)
        if cur.right is not None:
            self.__preorder(cur.right)

    # 중위순회
    def inorder_traverse(self):
        if self.head is not None:
            self.__inorder(self.head)

    def __inorder(self, cur):
        if cur.left is not None:
            self.__inorder(cur.left)

        self.inorder_list.append(cur.val)
        print(cur.val)

        if cur.right is not None:
            self.__inorder(cur.right)

    # 후위순회
    def postorder_traverse(self):
        if self.head is not None:
            self.__postorder(self.head)

    def __postorder(self, cur):
        if cur.left is not None:
            self.__postorder(cur.left)

        if cur.right is not None:
            self.__postorder(cur.right)

        self.postorder_list.append(cur.val)
        print(cur.val)


lst = [50, 30, 24, 5, 28, 45, 98, 52, 60]
bt = BinaryTree()
for num in lst:
    bt.add(num)


print(bt.search(60))
# 전우
bt.preorder_traverse()
print(bt.preorder_list)
# 중위
bt.inorder_traverse()
print(bt.inorder_list)
# 후위
bt.postorder_traverse()
print(bt.postorder_list)

# 출처: https://www.youtube.com/watch?v=0CqDdXOr6Kk