C++ 코딩테스트 강좌, 트리 순회하기

문제 설명

이 문제는 이진 트리를 구성하는 노드의 값을 특정 순서대로 출력하는 트리 순회 알고리즘을 구현하는 것입니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 자료구조로, 다양한 방식으로 노드를 방문할 수 있습니다. 가장 일반적인 트리 순회 방식은 전위 순회, 중위 순회, 후위 순회입니다.

트리의 정의

    struct TreeNode {
        int val; // 노드의 값
        TreeNode *left; // 왼쪽 자식 노드
        TreeNode *right; // 오른쪽 자식 노드
        TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 생성자
    };

접근 방법

각 순회의 접근 방법은 다음과 같습니다:

전위 순회 (Preorder Traversal): 현재 노드를 방문한 후, 왼쪽 자식 노드를 방문하고, 오른쪽 자식 노드를 방문합니다.
중위 순회 (Inorder Traversal): 왼쪽 자식 노드를 방문한 후, 현재 노드를 방문하고, 오른쪽 자식 노드를 방문합니다.
후위 순회 (Postorder Traversal): 왼쪽 자식 노드를 방문한 후, 오른쪽 자식 노드를 방문하고, 마지막으로 현재 노드를 방문합니다.

전위 순회 코드 구현

아래는 C++로 전위 순회를 구현한 코드입니다:

 
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorderTraversal(TreeNode* root, vector& result) {
    if (root == nullptr) return; // 기본 사례
    result.push_back(root->val); // 노드 방문
    preorderTraversal(root->left, result); // 왼쪽 서브트리 방문
    preorderTraversal(root->right, result); // 오른쪽 서브트리 방문
}

int main() {
    // 이진 트리 초기화
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    vector result;
    preorderTraversal(root, result);
    
    // 결과 출력
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

중위 순회 코드 구현

아래는 C++로 중위 순회를 구현한 코드입니다:


void inorderTraversal(TreeNode* root, vector& result) {
    if (root == nullptr) return; // 기본 사례
    inorderTraversal(root->left, result); // 왼쪽 서브트리 방문
    result.push_back(root->val); // 노드 방문
    inorderTraversal(root->right, result); // 오른쪽 서브트리 방문
}

// main 함수는 이전과 동일

후위 순회 코드 구현

아래는 C++로 후위 순회를 구현한 코드입니다:


void postorderTraversal(TreeNode* root, vector& result) {
    if (root == nullptr) return; // 기본 사례
    postorderTraversal(root->left, result); // 왼쪽 서브트리 방문
    postorderTraversal(root->right, result); // 오른쪽 서브트리 방문
    result.push_back(root->val); // 노드 방문
}

// main 함수는 이전과 동일

시간 복잡도 및 최적화

각 트리 순회 방법의 시간 복잡도는 O(n)입니다. 이는 트리의 모든 노드를 한 번씩 방문하기 때문입니다. 공간 복잡도는 트리가 완전하지 않을 경우 최악의 경우 O(h) (h는 트리의 높이)입니다. 만약 트리가 선형적인 형태라면 O(n) 공간이 필요할 수 있습니다.

최적화 방법

트리 순회 성능을 더욱 개선하기 위해 스택을 사용하여 반복적인 방법으로 구현할 수 있습니다. 예를 들어 전위 순회를 반복적으로 구현할 때는 다음과 같이 구현할 수 있습니다:


#include <stack>

void iterativePreorderTraversal(TreeNode* root, vector& result) {
    if (root == nullptr) return; 
    stack stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        result.push_back(node->val); // 노드 방문
        if (node->right != nullptr) stk.push(node->right); // 오른쪽 자식 먼저 추가
        if (node->left != nullptr) stk.push(node->left); // 왼쪽 자식 추가
    }
}

// main 함수는 이전과 동일

결론

이 강좌에서는 C++를 사용하여 이진 트리의 다양한 순회 알고리즘을 구현하는 방법을 설명했습니다. 각 순회의 방법론을 이해하고, 구체적인 코드를 작성하여 이를 실습하는 것이 중요합니다. 이진 트리는 다양한 분야에서 중요한 역할을 하므로 확실히 익혀두는 것이 좋습니다.