C++ でバイナリツリーデータ構造を実装する

C++ の二分木は、値と左右 2 つの子リンクを持つノード struct で表せます。以下の例では小さな木を構築し、ノード数を数え、辺の数で高さを測り、インオーダー走査で値を表示します。

ノードの struct で二分木を表す

二分木の各ノードが持つ子は最大 2 つで、慣例的に left と right と呼びます。struct はメンバーがデフォルトで public になるクラス型なので、この小さなデータ構造に適しています。各ノードは整数を保持し、子ノードを std::unique_ptr で所有します。null ポインターは子リンクがないことを示しますが、それだけでノードが葉になるわけではありません。葉とは、左右両方の子リンクが null であるノードです。

各ノードの子が 0 個または 2 個の二分木を full binary tree（全二分木）と呼びます。perfect binary tree（完全二分木）は全二分木であり、すべての葉が同じ深さにあります。以下で構築する木は全二分木ですが、complete binary tree（完備二分木）ではありません。最下段に、後続のノードより前の位置に空きがあります。これらの用語は異なる形状を表すため、混同しないでください。

小さな二分木を構築する

プログラムでは、走査順を追いやすい値を使い、次の形の木を決定的に構築します。8 (left: 3, right: 10 (left: 9, right: 14))

std::make_unique は各ノードを作成し、その所有権を持つポインターを返します。ポインターを子に移動すると所有権も移ります。そのためルートが木全体を所有し、ルートがスコープを抜けるとノードは自動的に解放されます。これにより、生の new による割り当てで必要になる手動の後片付けを避けられます。

以下の例を実行します。コード内の表示ラベル size、height、inorder は、コードをバイト単位で保持するため英語のままです。

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

各関数はノードへのポインターを受け取りますが、所有権は取得しません。root.get() を渡すと、所有する unique_ptr が木の寿命を管理したまま、関数から木にアクセスできます。同じ再帰的な定義は、どのような形の木にも使えます。

ノード数を数え、木の高さを求める

treeSize は、部分木がない場合に 0 を返します。それ以外の場合は現在のノードを数え、左右の部分木のサイズを加えます。treeHeight は、部分木がない場合に -1 を返し、左右の子の高さの大きい方に 1 を加えます。この規約では、ルートから葉までの最長経路に含まれる辺の数を高さとします。葉の高さは 0、上の木の高さは 2 です。ノード数で高さを数える定義もあり、その場合は葉の高さが 1 になります。どちらの規約を使うか決め、常に一貫させてください。

インオーダー走査でノードを表示する

printData は左の部分木をたどり、現在の値を表示してから右の部分木をたどります。これがインオーダー走査です。二分探索木なら値はソート順に表示されますが、一般の二分木ではこの走査順に並ぶだけです。詳しくはインオーダー走査のガイドを参照してください。

再帰を追うには、各ノードで関数がたどる順序を確認します。まず子がなくなるまで左へ進み、親へ戻りながら値を表示し、その後に右の部分木を処理します。そのため、この例の値は 3 8 9 10 14 の順になります。木のサイズは 5 ノード、高さは辺の数で 2 です。このプログラムは単独で動作します。ノードの値の型を変えたり操作を追加したりする場合は、所有権と高さの規約を明確に保ってください。