파이썬을 이용해서 순회 알고리즘을 구현해보자 ♻ (feat. DFS, BFS)

이전 포스트에서 이진 탐색 트리(Binary Search Tree)를 구현해보았습니다. 트리는 배열이나 스택, 큐등의 자료구조와는 달리 데이터를 직관적으로 살펴보기 어렵습니다. 따라서, 트리를 위한 별도의 순회 알고리즘이 필요합니다.

트리 순회 알고리즘

트리 순회 알고리즘은 트리에 저장된 모든 값을 중복이나 빠짐없이 살펴볼 때 사용합니다. 이진 트리의 순회 방법 중 깊이 우선 순회 방법(Depth First Traversal, DFS)으로는 전위 순회(Pre-order Traversal), 정위 순회(In-order Traversal), 후위 순회(Post-order Traversal)가 있으며, 너비 우선 순회 방법(Breadth First Traversal)으로는 레벨 순회(Level-order Traversal)가 있습니다. 이전 포스트에 구현한 BinarySearchTree() 클래스의 Method 형태로 차례로 구현해보았습니다.

아래 그림은 모두 [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47]의 데이터를 차례로 입력하여 만든 이진 탐색 트리입니다.

1. 깊이 우선 순회 (Depth First Traversal)

1.1. 전위 순회 (Pre-order Traversal)

뿌리(Root) 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 순회하는 알고리즘입니다. 구현 방법은 다음과 같습니다.

1. 노드를 방문한다
2. 왼쪽 서브 트리를 전위 순회한다
3. 오른쪽 서브 트리를 전위 순회한다

위의 트리의 경우 40 4 34 14 13 15 45 55 48 47 49 순서로 순회합니다.

class BinarySearchTree(object):
    ...
    def pre_order_traversal(self):
        def _pre_order_traversal(root):
            if root is None:
                pass
            else:
                print(root.data)
                _pre_order_traversal(root.left)
                _pre_order_traversal(root.right)
        _pre_order_traversal(self.root)

1.2. 정위 순회 (In-order Traversal)

왼쪽 서브트리 → 뿌리(Root) 노드 → 오른쪽 서브트리 순으로 순회합니다. 구현 방법은 다음과 같습니다.

1. 왼쪽 서브 트리를 정위 순회한다
2. 노드를 방문한다
3. 오른쪽 서브 트리를 정위 순회한다

위의 트리의 경우 4 13 14 15 34 40 45 47 48 49 55의 순서로 순회합니다. 이진 탐색 트리를 정위 순회하면 정렬된 데이터를 얻을 수 있습니다.

class BinarySearchTree(object):
    ...
    def in_order_traversal(self):
        def _in_order_traversal(root):
            if root is None:
                pass
            else:
                _in_order_traversal(root.left)
                print(root.data)
                _in_order_traversal(root.right)
        _in_order_traversal(self.root)

1.3. 후위 순회 (Post-order Traversal)

왼쪽 서브 트리 → 오른쪽 서브 트리 → 뿌리 노드 순으로 순회합니다. 구현 방법은 다음과 같습니다.

1. 왼쪽 서브 트리를 후위 순회한다
2. 오른쪽 서브 트리를 후위 순회한다
3. 노드를 방문한다

위의 트리의 경우 13 15 14 34 4 47 49 48 55 45 40 순으로 순회합니다.

class BinarySearchTree(object):
    ...
    def post_order_traversal(self):
        def _post_order_traversal(root):
            if root is None:
                pass
            else:
                _post_order_traversal(root.left)
                _post_order_traversal(root.right)
                print(root.data)
        _post_order_traversal(self.root)

2. 너비 우선 순회 (Breadth First Traversal)

2.1. 레벨 순회 (Level-order Traversal)

맨 위 뿌리 노드부터 너비 순으로 방문합니다. 아래의 코드는 위의 트리 노드를 40 4 45 34 55 14 48 13 15 47 49 순으로 순회합니다.

class BinarySearchTree(object):
    ...
    def level_order_traversal(self):
        def _level_order_traversal(root):
            queue = [root]
            while queue:
                root = queue.pop(0)
                if root is not None:
                    print(root.data)
                    if root.left:
                        queue.append(root.left)
                    if root.right:
                        queue.append(root.right)
        _level_order_traversal(self.root)

깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 알고리즘은 트리를 포함한 각종 그래프를 순회하는 데에 사용할 수 있습니다. 트리는 사이클을 가지지 않기 때문에, 구현시 이미 방문한 노드(visited)를 기억할 필요가 없습니다.

구현 결과 확인

이진 탐색 트리(Binary Search Tree)와 그 순회 알고리즘의 결과를 데이터를 넣어서 확인할 수 있습니다.

array = [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47]
 
bst = BinarySearchTree()
for x in array:
    bst.insert(x)
 
print(bst.find(15)) # True
print(bst.find(17)) # False
 
# depth first
bst.pre_order_traversal()   # 40 4 34 14 13 15 45 55 48 47 49
bst.in_order_traversal()    # 4 13 14 15 34 40 45 47 48 49 55
bst.post_order_traversal()  # 13 15 14 34 4 47 49 48 55 45 40
# breadth first
bst.level_order_traversal() # 40 4 45 34 55 14 48 13 15 47 49
 
bst.delete(55) # True
 
# depth first
bst.pre_order_traversal()   # 40 4 34 14 13 15 45 48 47 49
bst.in_order_traversal()    # 4 13 14 15 34 40 45 47 48 49
bst.post_order_traversal()  # 13 15 14 34 4 47 49 48 45 40
# breadth first
bst.level_order_traversal() # 40 4 45 34 48 14 47 49 13 15
 
bst.delete(14) # True
 
# depth first
bst.pre_order_traversal()   # 40 4 34 15 13 45 48 47 49
bst.in_order_traversal()    # 4 13 15 34 40 45 47 48 49
bst.post_order_traversal()  # 13 15 34 4 47 49 48 45 40
# breadth first
bst.level_order_traversal() # 40 4 45 34 48 15 47 49 13
 
bst.delete(11) # False
 
# depth first
bst.pre_order_traversal()   # 40 4 34 15 13 45 48 47 49
bst.in_order_traversal()    # 4 13 15 34 40 45 47 48 49
bst.post_order_traversal()  # 13 15 34 4 47 49 48 45 40
# breadth first
bst.level_order_traversal() # 40 4 45 34 48 15 47 49 13

참고

• http://ceadserv1.nku.edu/longa//classes/mat385_resources/docs/traversal.htm
• https://en.wikipedia.org/wiki/Binary_tree
• http://austingwalters.com/binary-trees-traversals-everyday-algorithms/
• https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/