C++ での二分探索木の挿入
この記事では、C++ で二分探索木データ構造の挿入関数を実装する方法を示します。
C++ の二分探索木に新しいノードを挿入する
二分木は、一般的にツリー構造のサブセットを表します。任意のノードに最大 2つの子があるため、これらはバイナリと呼ばれます。この場合、各ノードにキーと呼ばれるデータメンバーが含まれ、ツリーのすべてのレベルで、指定されたノードのキーが左側のサブツリーのキーより大きく、右側のすべてのキーより小さくなければならない二分探索木について説明します。サブツリー。この機能により、ソートされた配列で検索するときに、ツリーでバイナリ検索アルゴリズムを使用できるようになります。
最初に、ツリーノード struct を宣言する必要があります。これには、left/right ノードへの 2つのポインタとキーが含まれています。簡単にするために、キーを int 値として格納していますが、問題によってはノードの異なるレイアウトを作成する必要がある場合があります。また、ツリーのルートとして単一の TreeNode ポインタを宣言し、insertNode 関数を呼び出して新しいノードを追加することにより、このツリーを手動で構築します。
この例のデモンストレーションと検証を改善するために、指定されたキーを持つノードを検索する関数と、ツリー全体のコンテンツを出力する別の関数も含まれています。後者は、プログラムの各ステップでツリー構造を簡単に検査するのに役立ちます。ツリー構造は分割統治アルゴリズムに固有であるため、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);
}
}
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 関数では、2つの任意の int ベクトルを宣言し、それらの要素をツリーにプッシュします。insertNode 関数は、ルートノードとキー値の 2つのパラメーターを受け取ることに注意してください。指定されたルートノードが有効かどうか、または単に nullptr かどうかを確認する必要があります。後者は、関数がルートノードのコンテンツを作成する必要があることを示します。
ルートノードがすでに初期化されている場合、関数は現在のノードのキーと比較されるキー値に従って続行する必要があります。渡されたキーの値が指定されたキーよりも小さい場合は、左側のサブツリーに進む必要があります。それ以外の場合-正しいサブツリー。
最終的に、キーを格納する必要のあるノードに到達し、インオーダートラバーサルは、コードスニペットに示されているように、ソートされたキー値を常に出力します。
