C++에서 이진 검색 트리에 대한 중위 순회 구현
이 기사에서는 C++에서 이진 탐색 트리에 대한 중위 순회를 구현하는 방법을 설명합니다.
Inorder Traversal을 사용하여 이진 검색 트리의 내용 인쇄하기
이진 탐색 트리는 각 노드의 키가 왼쪽 하위 트리의 모든 키보다 크고 오른쪽 하위 트리의 모든 키보다 작아야 하도록 구성됩니다.
여기서는 단순함을 위해 불균형 트리만 고려하지만 실제 시나리오에서 이진 검색 트리의 효율성은 루트의 각 하위 트리가 대략적으로 동일한 높이를 갖는 균형 잡힌 특성에서 비롯됩니다.
이진 트리는 inorder, preorder 및 postorder라는 세 가지 다른 방법을 사용하여 탐색할 수 있습니다. 이진 탐색 트리에 대한 중위 순회는 내림차순으로 정렬된 요소를 생성합니다. 이 버전은 일반적으로 가장 왼쪽 노드에서 시작하여 왼쪽 하위 트리가 먼저 탐색되고 루트 노드가 탐색되고 마지막으로 오른쪽 하위 트리가 탐색되는 순서를 따릅니다.
다음 코드 스니펫 출력과 트리에 삽입된 정수의 순서에 주목하십시오.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreeInorder(TreeNode *n) {
if (n != nullptr) {
printTreeInorder(n->left);
cout << n->key << "; ";
printTreeInorder(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreeInorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 3; 5; 9; 11; 15; 20; 23;
또는 이진 검색 트리의 노드에 액세스하기 위해 사전 주문 또는 사후 주문 탐색을 사용해야 할 수도 있습니다. 순회 알고리즘을 수정하려면 printTree* 함수에서 cout << n->key << "; " 행만 이동하면 됩니다.
Preorder traversal은 루트 노드에서 인쇄를 시작한 다음 각각 왼쪽 및 오른쪽 하위 트리로 이동하는 반면 postorder traversal은 마지막에 루트 노드를 방문합니다.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreePreorder(TreeNode *n) {
if (n != nullptr) {
cout << n->key << "; ";
printTreePreorder(n->left);
printTreePreorder(n->right);
}
}
void printTreePostorder(TreeNode *n) {
if (n != nullptr) {
printTreePostorder(n->left);
printTreePostorder(n->right);
cout << n->key << "; ";
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreePostorder(root);
cout << endl;
printTreePreorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 9; 5; 3; 20; 15; 23; 11;
11; 3; 2; 5; 9; 23; 15; 20;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook