문제 설명
이 문제는 이진 트리를 구성하는 노드의 값을 특정 순서대로 출력하는 트리 순회 알고리즘을 구현하는 것입니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 자료구조로, 다양한 방식으로 노드를 방문할 수 있습니다. 가장 일반적인 트리 순회 방식은 전위 순회, 중위 순회, 후위 순회입니다.
트리의 정의
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++를 사용하여 이진 트리의 다양한 순회 알고리즘을 구현하는 방법을 설명했습니다. 각 순회의 방법론을 이해하고, 구체적인 코드를 작성하여 이를 실습하는 것이 중요합니다. 이진 트리는 다양한 분야에서 중요한 역할을 하므로 확실히 익혀두는 것이 좋습니다.