二分木の走査
二分探索木を生成し、再帰的なC++関数による先行順・中間順・後行順の走査をステップごとに確認します。
すべてこのブラウザ内でシミュレートされ、サーバーには一切送信されません。
ノード、左部分木、右部分木の順に訪問します。
ノード60で関数が呼び出される
ノード60で関数が呼び出される
二分木
出力
まだ訪問したノードがありません
- 未訪問
- 実行中
- スタック上
- 訪問済み
ステップ 1 / 44
コード
#include <iostream>
using namespace std;
class Node { // ノードは値と2つの子へのポインタを保持します
private: // プライベート属性:メソッドだけが触れます
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // node を根とする部分木を走査します
if (node == nullptr) return; // 基底ケース: 空の部分木には訪問するものがありません
cout << node->getValue() << " "; // ノードを訪問し、その値を処理します
preorder(node->getLeft()); // 左の部分木を走査します
preorder(node->getRight()); // 右の部分木を走査します
} // 呼び出し元に戻ります
Node* insert(Node* root, int v) { // v を探索木に挿入し、根を返します
if (root == nullptr) return new Node(v); // 空きの位置: 新しいノードはここに入ります
if (v < root->getValue()) // 小さい値は左へ、大きい値は右へ進みます
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // 値を1つずつ挿入して木を構築します
int values[] = {60, 45, 85, 68, 21, 55, 32}; // 表示中の木の値(挿入順)
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // アニメーションの木(構築済み)
preorder(root); // main からの最初の呼び出し
cout << endl; // 走査の終了
return 0;
}