[알고리즘] Morris Traversal

Morris Traversal for Preorder

 

트리를 순회하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중에서 Morris Traversal 알고리즘은 공간 복잡도를 O(1)로 유지하면서 순회할 수 있는 효율적인 방법으로 스택을 사용하지 않고도 Preorder Traversal를 수행할 수 있습니다.

 

따라서 메모리 사용에 제약이 있는 환경이거나 공간 복잡도를 최소화해야 하는 상황에서 유용하게 사용될 수 있습니다. 또한 추가 데이터 구조 없이 순회해야 하는 경우에도 유용하게 사용할 수 있습니다.

 

동작 순서

1. 현재 노드를 기준으로, 왼쪽 서브트리를 순회합니다.
2. 왼쪽 서브트리에서 현재 노드의 바로 이전 노드를 찾습니다.
3. 이전 노드의 오른쪽 자식을 현재 노드로 설정합니다.
4. 현재 노드를 방문합니다.
5. 현재 노드를 오른쪽 자식으로 이동합니다.

위 과정을 반복하여 모든 노드를 방문합니다.

 

파이썬 예시 

다음은 Morris Traversal 알고리즘을 사용하여 이진 트리를 Preorder 순회하는 예시 코드입니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_preorder_traversal(root):
    current = root
    while current:
        if current.left is None:
            print(current.val)  # 현재 노드를 방문
            current = current.right
        else:
            # 왼쪽 서브트리에서 현재 노드의 바로 이전 노드를 찾음
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if predecessor.right is None:
                print(current.val)  # 현재 노드를 방문
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                current = current.right

# 예시 이진 트리 생성
#      1
#    /   \
#   2     3
#  / \   / \
# 4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# Morris Traversal로 Preorder 순회하여 출력
print("Morris Preorder Traversal 결과:")
morris_preorder_traversal(root)

 

 

출처 : https://www.geeksforgeeks.org/morris-traversal-for-preorder/