C++에서 이진 트리 데이터 구조 구현
이 기사에서는 C++에서 이진 트리 데이터 구조를 구현하는 방법을 설명합니다.
C++에서struct키워드를 사용하여 이진 트리 구현
트리는 다양한 기본 알고리즘에서 사용되는 추상 데이터 구조입니다. 일반적으로 루트 노드와 하위 트리를 형성하는 자식이 있어야하는 계층 구조입니다. 또한 여러 트리 구조 유형이 있으며 각각 특정 요구 사항에 적합하고 몇 가지 절충안을 제공합니다.
이진 트리는 트리 데이터 구조의 하위 클래스 중 하나이며 각 노드에는left및right로 지정된 하위 노드를 포함하여 최대 2 개의 하위가 있어야하는 트리로 정의됩니다. 이 경우 기본적으로 멤버가 공용 인 클래스를 선언하므로struct함수를 사용하여 이진 트리를 구현합니다. 이진 트리의 노드에는 필요에 따라 왼쪽/오른쪽 노드와 데이터에 대한 두 개의 포인터가 있습니다. 설명 목적으로 만 노드에 저장된 데이터를 나타 내기 위해 단일int멤버를 선언했습니다.
정수를 인수로 사용하고data멤버를 해당 값으로 초기화하는 생성자를 정의합니다. 그런 다음nullptr값으로 2 노드 포인터를 초기화합니다. 이는 리프 노드를 나타내는 일반적인 방법입니다. 예제 드라이버 코드는 샘플 그래프를 생성하고 각 노드에 임의의 정수를 저장합니다. 이진 트리에는 여러 하위 유형이 있습니다. 예를 들어 전체 이진 트리는 모든 노드에0또는2자식이있는 구조입니다. 또 다른 하나는 완벽한 이진 트리로, 모든 내부 노드에는 두 개의 자식이 있고 모든 리프 노드는 동일한 깊이를 갖습니다.
#include <iostream>
#include <random>
using std::cout;
using std::endl;
struct BinTreeNode {
int data;
struct BinTreeNode *left;
struct BinTreeNode *right;
BinTreeNode() = default;
explicit BinTreeNode(int d) : data(d) {
left = nullptr;
right = nullptr;
}
};
constexpr int MIN = 1;
constexpr int MAX = 10000;
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
auto root = new BinTreeNode(distr(eng));
root->left = new BinTreeNode(distr(eng));
root->right = new BinTreeNode(distr(eng));
root->right->left = new BinTreeNode(distr(eng));
root->right->right = new BinTreeNode(distr(eng));
return EXIT_SUCCESS;
}
위의 코드는 다음 그래프에 표시된 것처럼 완전한 이진 트리 구조를 생성합니다. new연산자를 사용하여 각 노드를 할당하고 의사 난수 생성기를 사용하여 이니셜 라이저 값을 전달했습니다.
root / left right / \ / nullptr nullptr left right / \ /
nullptr nullptr nullptr nullptr
트리 구조의 크기와 높이를 계산하는 함수와 C++로 요소를 인쇄하는 함수 구현
트리 구조는 분할 및 정복 알고리즘이 실행되는 형식이므로 후자의 방법은 종종 요소를 조작하는 기능을 구현하는 데 사용됩니다. treeSize함수는 루트를 포함하여 모든 노드의 수를 나타내는 트리의 크기를 검색합니다. 단순 재귀를 사용하고root값 (1)의 크기와 왼쪽 / 오른쪽 노드의 크기 만 반환하면됩니다.
다음 함수는 트리의 높이를 검색하는treeHeight로, 일반적으로 루트에서 리프까지 가장 긴 경로에있는 노드의 양으로 알려져 있습니다. 이 함수는 또한 두 자식 노드에서 자신을 호출하고root값 (1)의 높이와 이전 호출에서 더 큰 값을 반환하여 재귀를 활용합니다.
반면에printData함수는 각 노드의data멤버를cout스트림으로 출력합니다. 이진 트리 구조에는 여러 순회 방법이 있습니다 : inorder, preorder 및 postorder 순회.
다음 예제에서는 순회 순회 방식이 사용됩니다. 이 프로세스는 처음에는 동일한 깊이에서 오른쪽으로 이동하는 가장 왼쪽 리프 노드의 데이터를 인쇄 한 다음 상위 수준으로 이동합니다. 다음 코드 조각은 부분적으로 임의의 이진 트리를 생성 한 다음 위의 각 함수를 호출합니다. 이러한 함수의 재귀 적 특성이 처음에 혼란스러워 보이면 더 작은 트리 개체에서 단계별로 디버깅을 시도하고 각 재귀 함수 호출의 동작을 관찰해야합니다.
#include <iostream>
#include <random>
using std::cout;
using std::endl;
struct BinTreeNode {
int data;
struct BinTreeNode *left;
struct BinTreeNode *right;
BinTreeNode() = default;
explicit BinTreeNode(int d) : data(d) {
left = nullptr;
right = nullptr;
}
};
int treeSize(BinTreeNode *n) {
if (n == nullptr)
return 0;
else
return 1 + treeSize(n->left) + treeSize(n->right);
}
int treeHeight(BinTreeNode *n) {
int lh, rh;
if (n == nullptr)
return -1;
else {
lh = treeHeight(n->left);
rh = treeHeight(n->right);
return 1 + (lh > rh ? lh : rh);
}
}
void printData(BinTreeNode *n) {
if (n != nullptr) {
printData(n->left);
cout << n->data << "; ";
printData(n->right);
}
}
constexpr int MIN = 1;
constexpr int MAX = 10000;
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
auto root = new BinTreeNode(distr(eng));
auto tmp = root;
auto iter = 100;
while (iter > 0) {
auto val = distr(eng);
if (val % 5 == 0) {
tmp->left = new BinTreeNode(distr(eng));
tmp = tmp->left;
} else if (val % 4 == 0) {
tmp->right = new BinTreeNode(distr(eng));
tmp = tmp->right;
} else if (val % 6 == 0) {
tmp->left = new BinTreeNode(distr(eng));
} else if (val % 100 == 0) {
tmp = root;
} else if (val % 2 == 0) {
tmp->right = new BinTreeNode(distr(eng));
}
iter -= 1;
}
cout << "size of tree = " << treeSize(root) << endl;
cout << "height of tree = " << treeHeight(root) << endl;
printData(root);
return EXIT_SUCCESS;
}
출력:
size of tree = 45
height of tree = 37
...(elements in the tree)
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