트리 순회 (Tree Traversal)

전위 순회(Preorder Traveral)

• 방문 순서: 루트→왼쪽 서브트리→오른쪽 서브트리
• 예를 들어서 트리가 다음 처럼 주어진다고 하자!

        1
       / \
      2   3
     / \   \
    4   5   6

• 이렇게 주어진다면 1-2-4-5-3-6의 방식으로 순회하게 된다!

코드로 작성한다면 다음과 같이 작성할 수 있다

void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->val << " "; // 루트 방문
    preorder(root->left);     // 왼쪽 서브트리 방문
    preorder(root->right);    // 오른쪽 서브트리 방문
}​

위의 코드처럼 만약 자식 노드가 없다면 return을 해주고 만약 자식 노드가 있다면 왼쪽을 먼저 하고 다음을 오른쪽으로 순회해 준다!

중위 순회(Inorder Traversal)

• 방문 순서: 왼쪽 서브트리→루트→오른쪽 서브트리
• 이전 예시의 트리로 예를 든다면 4-2-5-1-3-6의 순서로 탐색을 진행하게 된다!

코드로 작성한다면 다음과 같이 작성할 수 있다

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);     // 왼쪽 서브트리 방문
    cout << root->val << " "; // 루트 방문
    inorder(root->right);    // 오른쪽 서브트리 방문
}

중위 순회를 구하는 방식은 전위 순회랑 비슷하지만 왼쪽 서브트리를 순회를 한 다음에 오른쪽 서브트리를 방문한다는 것에서 차이점이 있다.

후위 순회(Postorder Traversal)

• 방문 순서:  왼쪽 서브트리→오른쪽 서브트리→루트
• 이전 예시의 트리로 예를 든다면 4-5-2-6-3-1의 순서로 탐색을 진행하게 된다!

코드로 작성한다면 다음과 같이 작성할 수 있다

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);     // 왼쪽 서브트리 방문
    postorder(root->right);    // 오른쪽 서브트리 방문
    cout << root->val << " ";  // 루트 방문
}​

 

여기에서는 왼쪽과 오른쪽을 다 방문한 다음에 루트노트를 방문하게 된다!

레벨 순회(Level-order Tarversal)

• 방문 순서: 루트-왼쪽-오른쪽 
• 단 방문을 하게 된다면 층별로 정점을 방문하게 된다.
• BFS탐색을 적용한다면 쉽게 표현할 수 있다.

벙식	순서	사용 방식
전위 순회	루트 → 왼쪽 → 오른쪽	복사, 수식 표기
중위 순회	왼쪽 → 루트 → 오른쪽	BST에서 정렬된 출력
후위 순회	왼쪽 → 오른쪽 → 루트	트리 삭제
레벨 순회	층별로 (BFS)	최단 경로 탐색