[Algorithm][그래프] 트리 순회(Tree Traversal)

트리 순회

이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 트리 순회에 대해서 알아보겠습니다.

트리 순회(Tree Traversal)란?

• 트리 구조에서 모든 노드를 특정한 순서로 한 번씩 방문하는 방법입니다.
• 트리는 계층적 자료구조이므로 단순히 선형적으로 탐색하는 게 아니라 노드 간의 부모-자식 관계를 고려한 탐색 방식이 필요합니다.
• 순회는 컴퓨터 구조, 파일 시스템 탐색, 수식 트리 평가 등 다양한 분야에서 활용됩니다.
• 순회 방법으로는 전위 순회, 중위 순회, 후위 순회가 있습니다.

 

❓ 왜 여러가지 순회 방법이 존재하나요?

• 트리는 방향성과 계층이 있는 구조이기 때문에 어떤 노드를 먼저 방문할지, 자식 노드를 언제 처리할지에 따라 의미가 달라지기 때문입니다.

전위 순회(Preorder Traversal)

• 자신(부모) 노드를 먼저 방문하고 왼쪽 → 오른쪽 자식 순으로 탐색하는 방법입니다.
• 트리 복사, 표현식 생성 등에 자주 사용됩니다.
• 수도 코드

Preorder(node):
    if node is not null:
        visit(node)                 // 현재 노드를 먼저 방문
        Preorder(node.left)   // 왼쪽 서브트리 순회
        Preorder(node.right) // 오른쪽 서브트리 순회

중위 순회(Inorder Traversal)

• 왼쪽 자식 노드들을 먼저 탐색하고 그다음 루트를 방문, 마지막으로 오른쪽 자식 노드들을 탐색합니다.
• 이진 탐색 트리(BST)에서 오름차순으로 정렬된 결과를 얻을 수 있는 순회입니다.
• 수도 코드

Inorder(node):
    if node is not null:
        Inorder(node.left)    // 왼쪽 서브트리 순회
        visit(node)               // 현재 노드 방문
        Inorder(node.right) // 오른쪽 서브트리 순회

후위 순회(Postorder Traversal)

• 왼쪽 → 오른쪽 자식 노드를 모두 방문하고 자신(부모) 노드를 탐색하는 방법입니다.
• 트리 구조 삭제나 하위 작업 완료 후 상위 작업을 해야 하는 경우에 적합합니다.
• 수도 코드

Postorder(node):
    if node is not null:
        Postorder(node.left)   // 왼쪽 서브트리 순회
        Postorder(node.right) // 오른쪽 서브트리 순회
        visit(node)                  // 현재 노드를 마지막에 방문

트리 순회 예제

        A
       /  \
      B   C
     /  \
    D   E

순회 방식	방문 순서
전위 순회	A → B → D → E → C
중위 순회	D → B → E → A → C
후위 순회	D → E → B → C → A

트리 순회 코드 구현하기

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100;

struct TreeNode {
    char data;
    int left;   // 왼쪽 자식의 인덱스
    int right;  // 오른쪽 자식의 인덱스
};

// 트리 배열 정의
TreeNode tree[MAX];
int root = 0; // 루트 노드 인덱스

// 전위 순회 (Preorder): 루트 → 왼쪽 → 오른쪽
void preorder(int idx) {
    if (idx == -1) return;
    cout << tree[idx].data << ' ';
    preorder(tree[idx].left);
    preorder(tree[idx].right);
}

// 중위 순회 (Inorder): 왼쪽 → 루트 → 오른쪽
void inorder(int idx) {
    if (idx == -1) return;
    inorder(tree[idx].left);
    cout << tree[idx].data << ' ';
    inorder(tree[idx].right);
}

// 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트
void postorder(int idx) {
    if (idx == -1) return;
    postorder(tree[idx].left);
    postorder(tree[idx].right);
    cout << tree[idx].data << ' ';
}

int main() {
    /*
            A
           / \
          B   C
         / \
        D   E
    */

    // 노드 구성
    tree[0] = {'A', 1, 2}; // A: left → B(1), right → C(2)
    tree[1] = {'B', 3, 4}; // B: left → D(3), right → E(4)
    tree[2] = {'C', -1, -1}; // C: 리프
    tree[3] = {'D', -1, -1}; // D: 리프
    tree[4] = {'E', -1, -1}; // E: 리프

    cout << "전위 순회 (Preorder): ";
    preorder(root);
    cout << "\n";

    cout << "중위 순회 (Inorder): ";
    inorder(root);
    cout << "\n";

    cout << "후위 순회 (Postorder): ";
    postorder(root);
    cout << "\n";

    return 0;
}

마무리하며

• 이번 글에서는 트리 자료구조에서 가장 핵심적인 개념 중 하나인 트리 순회(Tree Traversal) 방법에 대해 알아보았습니다.
• 전위 순회는 루트에서 시작해 좌우 자식을 방문하므로 트리의 구조를 저장하거나 복원할 때 유용합니다.
• 중위 순회는 이진 탐색 트리에서 오름차순 정렬된 결과를 얻는 데 자주 사용됩니다.
• 후위 순회는 자식 노드를 모두 처리한 후 부모를 방문하기 때문에 디렉토리 삭제와 같은 작업 순서에서 적합합니다.
• 트리 순회는 단순히 이론으로 끝나는 개념이 아니라 실전 알고리즘 문제와 자료구조 구현에 직접적으로 연결되는 주제입니다. 알고리즘의 기초를 다지는 데 꼭 필요한 개념이므로 직접 손으로 순회 순서를 그려보고 다양한 트리 구조에 적용해보면서 익숙해지는 것을 추천드립니다.