C++ でバイナリ検索ツリーデータ構造を実装する
このガイドでは、C++ でバイナリ検索ツリーデータ構造を実装する方法を示します。
C++ で struct キーワードを使用してバイナリ検索ツリーを実装する
二分探索木（BST）は、二分木データ構造の特殊なケースです。データ構造は通常、バイナリ検索アルゴリズムを使用して高速検索するために、要素のソートされたリストを格納するために使用されます。通常のバイナリツリーとは対照的に、BST には、各ノードに key と呼ばれる特別なデータメンバーがあり、一意の値を持っている必要があります。
BST のすべてのノードは、次の要件を満たす必要があります。key 値は、左側の子のサブツリー内のすべてのキーよりも大きく、右側の子のサブツリー内のすべてのキーよりも小さい必要があります。前のステートメントは、キー値が小さい要素がツリー階層の左側に配置されることを意味します。これにより、バイナリ検索を使用するのに最適な構造が得られます。
次のサンプルコードでは、BSTreeNode という名前の struct を定義します。これは、左右のノードへの 2つのポインタと、キーを示す string メンバーで構成されます。キー値がノードに格納されているデータと同じである、最も単純なバージョンの 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 には、挿入、削除、ルックアップの 3つの主要な操作が実装されています。
次の例では、ルックアップに重点を置いています。findNode 関数は、ルートノードを使用して関数に渡される BST 内の指定されたキーのルックアップを担当します。このコマンドは再帰的な性質のものであり、キーが格納されている BSTreeNode へのポインタを返します。キー値がどのノードにも見つからない場合は、nullptr が返されます。より良いデモンストレーションのために、ノードポインターを受け取り、キー値を cout ストリームに出力して、findNode 関数の戻り値を関数に直接チェーンして出力する printNode 関数も実装しました。
#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!
