[c++] 트리 순회 알고리즘

08 Dec 2023

트리 구조는 계층적인 데이터를 표현하는 데 유용한 자료구조입니다. 트리의 각 노드는 다른 노드들과의 연결로 이루어져 있으며, 각 노드는 자식 노드를 가질 수 있습니다. 트리를 순회(traversal) 한다는 것은 트리의 모든 노드를 한 번씩 방문하는 것을 의미합니다. C++에서는 트리를 순회하는 다양한 알고리즘이 존재합니다.

전위 순회 (Pre-order traversal)

전위 순회는 루트 노드를 가장 먼저 방문한 후, 왼쪽 서브트리를 순회한 뒤, 오른쪽 서브트리를 순회하는 방식입니다. 전위 순회 알고리즘은 다음과 같이 구현할 수 있습니다.

void preorderTraversal(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " "; // 노드 방문
    preorderTraversal(root->left); // 왼쪽 서브트리 순회
    preorderTraversal(root->right); // 오른쪽 서브트리 순회
}

중위 순회 (In-order traversal)

중위 순회는 왼쪽 서브트리를 먼저 순회한 후, 루트 노드를 방문하고, 오른쪽 서브트리를 순회하는 방식입니다. 중위 순회 알고리즘은 다음과 같이 구현할 수 있습니다.

void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left); // 왼쪽 서브트리 순회
    cout << root->data << " "; // 노드 방문
    inorderTraversal(root->right); // 오른쪽 서브트리 순회
}

후위 순회 (Post-order traversal)

후위 순회는 왼쪽 서브트리를 먼저 순회한 후, 오른쪽 서브트리를 순회한 뒤에 루트 노드를 방문하는 방식입니다. 후위 순회 알고리즘은 다음과 같이 구현할 수 있습니다.

void postorderTraversal(Node* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left); // 왼쪽 서브트리 순회
    postorderTraversal(root->right); // 오른쪽 서브트리 순회
    cout << root->data << " "; // 노드 방문
}

이와 같이 C++에서는 트리를 전위, 중위, 후위 순회하는 알고리즘이 간단하게 구현될 수 있습니다.

References

Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein