C++에서 이진 검색 트리 데이터 구조 구현
이 가이드는 C++에서 이진 검색 트리 데이터 구조를 구현하는 방법을 보여줍니다.
C++에서struct키워드를 사용하여 이진 검색 트리 구현
이진 검색 트리 (BST)는 이진 트리 데이터 구조의 특수한 경우입니다. 데이터 구조는 일반적으로 이진 검색 알고리즘을 사용하여 빠른 검색을 위해 정렬 된 요소 목록을 저장하는 데 사용됩니다. 일반 이진 트리와 달리 BST에는키라는 각 노드에 고유 한 값이 있어야하는 특수 데이터 멤버가 있습니다.
BST의 모든 노드는 다음 요구 사항을 충족해야합니다.key값은 왼쪽 자식의 하위 트리에있는 모든 키보다 크고 오른쪽 자식의 하위 트리에있는 모든 키보다 작아야합니다. 이전 명령문은 더 작은 키 값을 가진 요소가 트리 계층 구조의 왼쪽에 위치 함을 의미합니다. 이진 검색을 사용하기위한 최적의 구조가됩니다.
다음 예제 코드에서는 왼쪽/오른쪽 노드에 대한 두 개의 포인터와 키를 나타내는string멤버로 구성된BSTreeNode라는struct를 정의합니다. 키 값이 노드에 저장된 데이터와 동일한 가장 간단한 버전의 BST를 구현하고 있다는 점에 유의하십시오.
일반적으로 프로그래머는 특정 문제에 필요한 다른 데이터 멤버를 저장하기 위해 BST 노드를 자유롭게 정의 할 수 있습니다. 이 정의는 지정된 문자열 (키)을 검색해야하는 정렬 된 문자열 배열을 에뮬레이션하는 데 가장 적합합니다. 이진 검색 기능을 구현하기 전에 BST 개체를 처음부터 구성해야합니다. 따라서 사전 정의 된 문자열벡터를 사용하여 새로운 이진 검색 트리를 초기화합니다.
insertNode함수는 트리의 루트가 인수로 전달 될 때 새 하위BSTreeNode를 작성하는 재귀 적 구현입니다. 루트 노드 자체를 만들어야하는 경우BSTreeNode유형에 대한 포인터를 선언하고 여기에nullptr를 할당 한 다음 여기에 저장해야하는 해당string값과 함께insertNode에 전달할 수 있습니다. v1내용으로 목록을 초기화하면printTree함수를 호출하여 BST의inorder순회라고하는 정렬 된 순서로 모든 키 값을 인쇄 할 수 있습니다.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct BSTreeNode {
string key;
struct BSTreeNode *left{};
struct BSTreeNode *right{};
};
void insertNode(BSTreeNode *&root, const string &k) {
if (root == nullptr) {
root = new BSTreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTree(BSTreeNode *n) {
if (n != nullptr) {
printTree(n->left);
cout << n->key << "; ";
printTree(n->right);
}
}
int main() {
std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};
BSTreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTree(root);
return EXIT_SUCCESS;
}
출력:
aim; born; camel; maya; wind; xen; zero;
C++에서 이진 검색 트리에 대한 이진 검색 알고리즘 구현
이진 검색 알고리즘은 키가 계층 구조에 저장되는 순서 때문에 BST 구조에서 효율적입니다. BST에 대해 구현되는 세 가지 주요 작업은 삽입, 삭제 및 조회입니다.
다음 예에서는 조회에 더 중점을 둡니다. findNode함수는 루트 노드를 사용하여 함수로 전달되는 BST에서 주어진 키의 조회를 담당합니다. 이 명령은 재귀 적 특성이며 키가 저장된BSTreeNode에 대한 포인터를 리턴합니다. 노드에서 키 값을 찾을 수 없으면nullptr이 반환됩니다. 더 나은 데모를 위해 노드 포인터를 가져와cout스트림에 키 값을 출력하는printNode함수도 구현하여findNode함수 반환 값을 함수에 직접 연결하여 인쇄했습니다.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct BSTreeNode {
string key;
struct BSTreeNode *left{};
struct BSTreeNode *right{};
};
void insertNode(BSTreeNode *&root, const string &k) {
if (root == nullptr) {
root = new BSTreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
BSTreeNode *findNode(BSTreeNode *root, const string &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 printNode(BSTreeNode *n) {
if (n != nullptr) {
cout << n->key << endl;
} else {
cout << "Not a valid node!" << endl;
}
}
int main() {
std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};
BSTreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printNode(findNode(root, "zero"));
printNode(findNode(root, "zeroo"));
return EXIT_SUCCESS;
}
출력:
zero
Not a valid node!
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