C++の再帰を使って木（ツリー）のサイズを計算するプログラムの作成方法

この問題では、二分木が与えられ、「再帰」を使って木のサイズを計算するプログラムを作成することが課題となります。

ここでいう木のサイズとは、その木に含まれるノードの総数のことです。

具体例を見ながら問題を理解していきましょう。

上の木の場合、サイズは 5 となります。

解法の考え方：再帰によるサイズ計算

木のサイズを求めるには、左部分木のサイズ + 右部分木のサイズ + 1（現在のノード） を計算します。再帰関数は、木の左右それぞれの部分木に対して呼び出され、部分木が存在しない（NULL の）場合は 0 を返します。

上記の例をこの手法で解いてみる

ルート（値3）のサイズを求める場合：

• size(3) = size(5) + size(7) + 1
• size(3) = (size(1) + size(9) + 1) + 1 + 1
• size(3) = (1 + 1 + 1) + 1 + 1
• size(3) = 5

C++での実装例

それでは、この解法の動作を示すプログラムを見てみましょう。

#include <iostream>
using namespace std;
class node {
    public:
    int data;
    node* left;
    node* right;
};
node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}
int findSize(node* node) {
    if (node == NULL)
        return 0;
    else
        return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
    node *root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(7);
    root->left->left = insertNode(1);
    root->left->right = insertNode(5);
    root->right->left = insertNode(2);
    cout<<"与えられた木のサイズは "<<findSize(root);
    return 0;
}

実行結果

与えられた木のサイズは 6

計算量について

このアルゴリズムの時間計算量は O(n) です（n はノードの総数）。すべてのノードを一度ずつ訪問するためです。また、再帰呼び出しによるスタック領域の使用があり、空間計算量は木の高さ h に依存し、O(h) となります。平衡な二分木であれば O(log n)、最悪ケース（線形に連なる木）では O(n) になります。