C++ でバイナリツリーデータ構造を実装する
この記事では、C++ でバイナリツリーデータ構造を実装する方法について説明します。
C++ で struct キーワードを使用してバイナリツリーを実装する
ツリーは、さまざまな基本的なアルゴリズムで使用される抽象的なデータ構造です。これらは一般に階層構造であり、ルートノードとその子がサブツリーを形成する必要があります。また、複数のツリー構造タイプがあり、それぞれが特定のニーズに適しており、いくつかのトレードオフを提供します。
二分木はツリーデータ構造のサブクラスの 1つであり、left と right として指定された子ノードを含め、各ノードに最大 2つの子が必要なツリーとして定義されます。この場合、メンバーがデフォルトでパブリックであるクラスを宣言するため、struct 関数を使用してバイナリツリーを実装します。バイナリツリーのノードには、必要に応じて、左右のノードとデータへの 2つのポインタが含まれています。説明のみを目的として、ノードに格納されているデータを表す単一の int メンバーを宣言したことに注意してください。
整数を引数として取り、その値で data メンバーを初期化するコンストラクターを定義します。次に、2 ノードポインタを nullptr 値で初期化します。これは、リーフノードを示す一般的な方法です。サンプルのドライバーコードは、サンプルグラフを作成し、各ノードにランダムな整数を格納します。バイナリツリーには複数のサブタイプがあります。たとえば、完全なバイナリツリーは、すべてのノードに 0 または 2 の子がある構造です。もう 1つは完全な二分木と呼ばれ、すべての内部ノードに 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 関数は、各ノードから cout ストリームに data メンバーを出力します。二分木構造には複数のトラバーサル方法があります。インオーダー、プレオーダー、およびポストオーダートラバーサルです。
次の例では、順序どおりの走査方法が使用されています。このプロセスでは、最初に同じ深さで右に行く左端のリーフノードからデータを出力してから、上位レベルに移動します。次のコードスニペットは、部分的にランダムなバイナリツリーを構築し、その上で上記の各関数を呼び出します。これらの関数の再帰的な性質が一見混乱しているように見える場合は、小さなツリーオブジェクトで段階的にデバッグを試み、各再帰的な関数呼び出しの動作を観察する必要があります。
#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)
