C++で二分木の最大幅を求めるアルゴリズムと実装例

問題文

二分木が与えられたとき、その木の最大幅を求める関数を実装します。ここでいう「木の幅」とは、あるレベル（深さ）に存在するノードの数のことです。木の最大幅は、すべてのレベルの幅の中で最も大きな値となります。

以下の二分木を例に考えてみましょう。

      10
     / \
    7   4
   / \   \
  9   2   1
         / \
        2   5

この木の各レベルの幅は次のようになります。

• レベル1の幅：1（ルートのみ）
• レベル2の幅：2（7 と 4）
• レベル3の幅：3（9・2・1）
• レベル4の幅：2（2 と 5）

したがって、この二分木の最大幅は 3 です。

アルゴリズム

この問題はレベル順走査（Level Order Traversal）の考え方を利用して解くことができます。手順は以下の通りです。

1. 再帰的に木の高さを求める。
2. レベル1から木の高さまで、各レベルごとのノード数（幅）を計算する。
3. 全レベルの幅のうち最大の値を答えとして返す。

getWidth 関数は、指定されたレベルに存在するノードの個数を再帰的に数えます。レベルが1（ルートの位置）であれば1を返し、より深いレベルの場合は、左部分木と右部分木それぞれにおける該当レベルのノード数を合計した値を返します。

計算量についても確認しておきましょう。高さの計算に O(n)、各レベルの幅の計算にも最大 O(n) かかるため、全体の時間計算量は O(n × h)（h は木の高さ、最悪の偏った木では O(n²)）となります。空間計算量は再帰呼び出しのスタック分の O(h) です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct node {
public:
    int data;
    node* left;
    node* right;
};
int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);
int getMaxWidth(node* root){
    int maxWidth = 0;
    int width;
    int h = height(root);
    int i;
    for (i = 1; i <= h; ++i) {
        width = getWidth(root, i);
        if (width > maxWidth) {
            maxWidth = width;
        }
    }
    return maxWidth;
}
int getWidth(node* root, int level){
    if (root == NULL) {
        return 0;
    }
    if (level == 1) {
        return 1;
    }
    else if (level > 1) {
        return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
    }
}
int height(node* node){
    if (node == NULL) {
        return 0;
    }
    int lHeight = height(node->left);
    int rHeight = height(node->right);
    return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}
node* newNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}
int main(){
    node *root = newNode(10);
    root->left = newNode(7);
    root->right = newNode(4);
    root->left->left = newNode(9);
    root->left->right = newNode(2);
    root->right->right = newNode(1);
    root->right->right->left = newNode(2);
    root->right->right->right = newNode(5);
    cout<<"Maximum width = " << getMaxWidth(root) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum width = 3