C++의 이진 검색 트리 삽입
이 기사에서는 C++에서 이진 검색 트리 데이터 구조에 대한 삽입 기능을 구현하는 방법을 보여줍니다.
C++의 이진 검색 트리에 새 노드 삽입
이진 트리는 일반적으로 트리 구조의 하위 집합을 나타냅니다. 주어진 노드에 최대 두 개의 자식이 있기 때문에 이진이라고 불립니다. 이 경우, 각 노드가 키라는 데이터 멤버를 포함하는 이진 검색 트리에 대해 논의하며, 트리의 모든 레벨에서 주어진 노드의 키는 왼쪽 하위 트리의 키보다 크고 오른쪽 하위 트리의 모든 키보다 작아야 한다. 이 기능을 사용하면 정렬된 배열에서 검색할 때 트리에서 이진 검색 알고리즘을 사용할 수 있습니다.
먼저 left/right 노드에 대한 두 개의 포인터와 키를 포함하는 트리 노드 struct를 선언해야 합니다. 단순화를 위해 키를 int 값으로 저장하지만 문제에 따라 노드에 대해 다른 레이아웃을 구성해야 할 수도 있습니다. 또한 단일 TreeNode 포인터를 트리의 루트로 선언한 다음 insertNode 함수를 호출하여 새 노드를 추가하여 이 트리를 수동으로 구성합니다.
예제의 더 나은 시연과 검증을 위해 주어진 키를 가진 노드를 찾는 기능과 전체 트리의 내용을 인쇄하는 또 다른 기능을 포함합니다. 후자는 프로그램의 각 단계에서 트리 구조를 쉽게 검사하는 데 도움이 됩니다. 트리 구조가 분할 및 정복 알고리즘에 내재되어 있으므로 세 가지 기능 모두 재귀를 사용합니다.
#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);
}
}
TreeNode *findNode(TreeNode *root, const int k) {
if (root == nullptr) return nullptr;
if (k == root->key) return root;
if (k < root->key)
return findNode(root->left, k);
else
return findNode(root->right, k);
}
void printTree(TreeNode *n) {
if (n != nullptr) {
printTree(n->left);
cout << n->key << "; ";
printTree(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);
}
printTree(root);
cout << endl;
std::vector<int> v2{1, 22, 4, 16};
for (const auto &item : v2) {
insertNode(root, item);
}
printTree(root);
cout << endl;
return EXIT_SUCCESS;
}
출력:
2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;
main 함수에서 두 개의 임의의 int 벡터를 선언한 다음 해당 요소를 트리에 푸시합니다. insertNode 함수는 루트 노드와 키 값이라는 두 개의 매개변수를 사용합니다. 주어진 루트 노드가 유효한지 또는 단지 nullptr인지 확인해야 하며, 후자는 함수가 루트 노드 내용을 생성해야 함을 나타냅니다.
루트 노드가 이미 초기화되어 있으면 현재 노드의 키와 비교한 키 값에 따라 기능이 진행되어야 합니다. 전달된 키의 값이 주어진 키보다 작으면 왼쪽 하위 트리로 이동해야 합니다. 그렇지 않으면 - 오른쪽 하위 트리.
결국, 우리는 키를 저장해야 하는 노드에 도달할 것이고, 순서 순회는 항상 코드 조각에 설명된 대로 정렬된 키 값을 인쇄합니다.
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