[Python] 트리 순회 알고리즘

이전 포스팅에서 이진 탐색 트리를 구현해보았다. 이번에는 트리 순회 알고리즘을 살펴보도록 하자. 트리를 위한 별도의 순회 알고리즘이 있는데 이또한 재귀적으로 간단하게 구현할 수 있다.

트리 순회 알고리즘

트리에 있는 노드들을 다 살펴보고 확인하고 싶을 때 사용한다. 순회 알고리즘에는 전위 순회(pre-order traversal), 후위 순회(post-order traversal), 정위 순회(in-order traversal), 레벨 순회(level-order traversal) 등이 있다. 이 중 정위 순회를 통해 이진 트리에서 정렬된 데이터를 얻을 수 있다. 이 글에서의 순회 알고리즘은 이전 포스팅에서의 BinarySearchTree를 재귀적으로 구현한 클래스의 메소드 형식으로 구현되어있다. 

전위 순회(pre-order traversal)

 

출처: https://austingwalters.com/binary-trees-traversals-everyday-algorithms/

 

전위 순회는 뿌리 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회한다.

 

    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)

 

후위 순회(post-order traversal)

출처: https://austingwalters.com/binary-trees-traversals-everyday-algorithms/

 

후위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 뿌리 노드 순으로 순회한다.

 

    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)

 

정위 순회(in-order traversal)

 

출처: https://austingwalters.com/binary-trees-traversals-everyday-algorithms/

 

정위 순회는 왼쪽 서브 트리 -> 뿌리 노드 -> 오른쪽 서브 트리 순으로 순회한다.

 

    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)

 

전위 순회, 후위 순회, 정위 순회는 깊이 우선 순회방식의 알고리즘으로 재귀적이게 간단하게 구현할 수 있었다. 남은 레벨 순회는 너비 우선 순회방식으로 구현한다.

 

레벨 순회(level-order traversal)

출처: https://austingwalters.com/binary-trees-traversals-everyday-algorithms/

 

    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)

 

결과 확인

 

array = [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47]

bst = BinarySearchTree()
for x in array:
    bst.insert(x)

bst.pre_order_traversal()   # 40 4 34 14 13 15 45 55 48 47 49
print()
bst.in_order_traversal()    # 4 13 14 15 34 40 45 47 48 49 55
print()
bst.post_order_traversal()  # 13 15 14 34 4 47 49 48 55 45 40
print()
bst.level_order_traversal() # 40 4 45 34 55 14 48 13 15 47 49
print()

bst.delete(55)
print()

bst.pre_order_traversal()   # 40 4 34 14 13 15 45 48 47 49
print()
bst.in_order_traversal()    # 4 13 14 15 34 40 45 47 48 49
print()
bst.post_order_traversal()  # 13 15 14 34 4 47 49 48 45 40
print()
bst.level_order_traversal() # 40 4 45 34 48 14 47 49 13 15
print()

 

 

참고

• http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html
• https://austingwalters.com/binary-trees-traversals-everyday-algorithms/