이진 트리의 순회 알고리즘은 재귀적으로 각 노드를 방문합니다. 각 순회 방법(전위, 중위, 후위)는 방문 순서를 결정합니다. 전위, 중위, 후위의 차이는 루트 노드를 몇 번째로 탐색하느냐?? 차이입니다.
- 전위 순회(Pre-order Traversal): 루트를 먼저 방문한 다음, 왼쪽 서브트리와 오른쪽 서브트리를 방문합니다.
- 중위 순회(In-order Traversal): 왼쪽 서브트리를 먼저 방문한 다음, 루트를 방문하고, 마지막으로 오른쪽 서브트리를 방문합니다.
- 후위 순회(Post-order Traversal): 왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문한 다음, 루트를 방문합니다.
다음은 C++로 작성된 이진 트리 순회 알고리즘입니다.
#include <iostream>
template<typename T>
class BinaryTree {
private:
struct Node {
T value;
Node *left, *right;
Node(T val) : value(val), left(nullptr), right(nullptr) {}
~Node() {
delete left;
delete right;
}
};
Node *root;
void preOrderTraversal(Node *node) {
if (node == nullptr) return;
std::cout << node->value << " ";
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
void inOrderTraversal(Node *node) {
if (node == nullptr) return;
inOrderTraversal(node->left);
std::cout << node->value << " ";
inOrderTraversal(node->right);
}
void postOrderTraversal(Node *node) {
if (node == nullptr) return;
postOrderTraversal(node->left);
postOrderTraversal(node->right);
std::cout << node->value << " ";
}
public:
BinaryTree() : root(nullptr) {}
void insert(T value) {
if (root == nullptr) {
root = new Node(value);
} else {
// 더 복잡한 삽입 로직을 구현할 수 있습니다.
}
}
void preOrder() {
preOrderTraversal(root);
std::cout << std::endl;
}
void inOrder() {
inOrderTraversal(root);
std::cout << std::endl;
}
void postOrder() {
postOrderTraversal(root);
std::cout << std::endl;
}
~BinaryTree() {
delete root;
}
};