C++ で二分探索木の順序トラバーサルを実装する
胡金庫
2023年10月12日
この記事では、C++ で二分探索木の順序トラバーサルを実装する方法について説明します。
順序トラバーサルを使用して、二分探索木の内容を出力する
二分探索木は、各ノードのキーが左側のサブツリーのすべてのキーよりも大きく、右側のサブツリーのすべてのキーよりも小さくなければならないように構築されます。
ここでは簡単にするために不均衡なツリーのみを考慮しますが、実際のシナリオでは、バイナリ検索ツリーの効率は、ルートの各サブツリーの高さがほぼ同じであるバランスの取れた性質に由来します。
二分木は、inorder、preorder、postorder という名前の 3つの異なる方法を使用してトラバースできます。二分探索木の順序トラバーサルは、降順ではない順序でソートされた要素を生成します。このバージョンは通常、左端のノードから始まり、左のサブツリーが最初にトラバースされ、次にルートノード、最後に右のサブツリーがトラバースされる順序に従います。
次のコードスニペット出力と、ツリーに挿入された整数の順序に注意してください。
#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 << "; "行を移動するだけです。
プレオーダートラバーサルはルートノードから出力を開始し、次にそれぞれ左と右のサブツリーに移動しますが、ポストオーダートラバーサルは最後にルートノードにアクセスします。
#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;
著者： 胡金庫
