【C++入門】二分木の最大の深さ（高さ）を求めるプログラムの作成方法

本記事では、二分木（バイナリツリー）が与えられたときに、その木の最大の深さ（高さ）を求めるプログラムをC++で作成する方法を解説します。

問題の理解

まず、具体的な例を使って問題を確認しましょう。

上図の二分木の高さは 3 です。

アプローチ：再帰による高さの計算

木の最大の高さを求める基本的な考え方は次のとおりです。

• 着目しているノードの左部分木と右部分木の高さをそれぞれ求める
• 両者のうち大きい方に1を加えた値が、そのノードを根とする木の高さになる

この処理は再帰的に行われます。木の末端（葉）のノードに到達するまで再帰呼び出しが続き、戻りながら各部分木の高さに1ずつ加算していくことで、最終的に木全体の高さが求まります。

例題を手順どおりに解いてみる

根のノード（値3）の高さは、次の式で表せます。

height(3) = max(height(5), height(7)) + 1

このために、値5と7を持つノードの高さを計算します。

• height(5) = max(height(1), height(9)) + 1
• height(7) = 1（子ノードを持たないため）

さらに、height(1) = height(9) = 1 なので、

• height(5) = max(1, 1) + 1 = 2
• height(3) = max(2, 1) + 1 = 3

したがって、この二分木の高さは 3 となります。

C++での実装例

上記の解法を実装したプログラムがこちらです。

#include <iostream>
using namespace std;

// 二分木のノードを表すクラス
class node {
    public:
    int data;
    node* left;
    node* right;
};

// 木の高さを再帰的に計算する関数
int height(node* node) {
    if (node == NULL)
        return 0;
    else {
        int lDepth = height(node->left);  // 左部分木の高さ
        int rDepth = height(node->right); // 右部分木の高さ
        if (lDepth > rDepth)
            return(lDepth + 1);
        else
            return(rDepth + 1);
    }
}

// 新しいノードを生成する関数
node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}

int main() {
    // 例題と同じ構造の二分木を構築
    node *root = insertNode(3);
    root->left = insertNode(5);
    root->right = insertNode(7);
    root->left->left = insertNode(1);
    root->left->right = insertNode(9);

    cout<<"与えられた二分木の高さは "<<height(root);
    return 0;
}

コードの解説

• nodeクラス：木の各ノードを表現します。格納するデータ（data）と、左の子・右の子へのポインタ（left / right）を持ちます。
• height関数：再帰の核となる部分です。ノードがNULL（空）なら0を返し、そうでなければ左右の部分木の高さを再帰的に求めて、大きい方に1を加えて返します。
• insertNode関数：新しいノードを動的に生成し、初期化して返すヘルパー関数です。
• main関数：例題と同じ構造の二分木を構築し、height関数を呼び出して結果を表示します。

実行結果

与えられた二分木の高さは 3

計算量の分析

• 時間計算量：O(n) — nはノードの総数です。すべてのノードをちょうど一度ずつ訪問するため、線形時間で処理できます。
• 空間計算量：O(h) — hは木の高さです。再帰呼び出しのスタックの深さが木の高さに依存します。

まとめ

二分木の高さを求める問題は、「左右の部分木の高さの最大値＋1」というシンプルな再帰関係で解決できます。再帰の考え方に慣れるための練習問題としても最適なので、ぜひ自分でもコードを書いて動かしてみてください。