순회 (Traversal) 란?

순회 기본개념(Traversal)

순회는 Traversal로 명명되며, 그래프 또는 트리처럼 연결된 구조에서 노드를 한 번씩 탐색하는 개념이다.

• 순회의 목적은 모든 노드 또는 특정 노드를 방문하는 방법을 찾는 것이다.
• BST(이진검색트리)와 다른 규칙이 적용되며 방향에 따라 탐색방법이 달라질 수 있다.

그래프와 트리의 순회구분

• 그래프의 순회는 DFS(깊이우선탐색), BFS(너비우선탐색) 방법이 있다.
  • DFS, BFS는 탐색 알고리즘이다.
• 트리의 순회는 전위, 중위, 후위순회이다.
  • 그래프는 루트, 부모, 자식노드 개념이 없지만 전위, 중위, 후위순회의 순회개념을 활용하여 DFS, BFS를 구현할 수 있다.

• 전위 순회(preorder traverse) : 루트를 먼저 방문
• 중위 순회(inorder traverse) : 왼쪽 서브 트리를 방문 후 루트 방문
• 후위 순회(postorder traverse) : 순서대로 서브 트리(왼쪽->오른쪽)를 모두 방문 후 루트를 방문

트리에 대한 순회 구현

먼저 어떤 결과가 나올 것인지 예상 해보기 위해 서브 트리를 구분 해 놓으면 헷갈리는 경우를 방지할 수 있다.

• 루트는 1개(10)이다.
• 부모 노드는 트리 별 1개 씩 이니 총 4개이다.(8, 1, 9, 12)

# 수도코드
# 먼저 순회를 진행하기 위해 트리형태의 노드들을 생성한다.

class node:
    # root -> left -> right 방향대로 노드 생성
    def __init__(self, value, left=None, right=None):
        value
        left
        right

root_node = node(10,
                 node(8,
                      node(7),
                      node(1,
                           node(3), node(2)
                          )
                      ),
                 node(9,
                      node(11),
                      node(12,
                           node(13)
                          )
                      )
                 )

# 전위 순회
def pre_order(node):
    print(node.value)       # 루트노드
    pre_order(node.left)    # 왼쪽노드
    pre_order(node.right)   # 오른쪽노드

# 중위 순회
def in_order(node):
    in_order(node.left)    # 왼쪽노드
    print(node.value)      # 루트노드
    in_order(node.right)   # 오른쪽노드

# 후위 순회
def post_order(node):
    post_order(node.left)   # 왼쪽노드
    post_order(node.right)  # 오른쪽노드
    print(node.value)       # 루트노드