C++で二分木の完全ノードを数える方法（反復法と再帰法）

本記事では、二分木に含まれる「完全ノード（フルノード）」の数を、反復法と再帰法の2つのアプローチで求める方法を解説します。完全ノードとは、左と右の子を両方持ち、どちらの子もNULLでないノードのことです。つまり、ちょうど2つの子を持つノードのみが完全ノードとして扱われます。

二分木はデータの格納に用いられる特殊なデータ構造です。「各ノードが最大2つの子までしか持てない」という制約があり、ソート済み配列並みの高速な検索性能と、連結リスト並みの高速な挿入・削除性能を兼ね備えているのが特徴です。なお、1つ以上の子を持つ非葉ノードは「親ノード」とも呼ばれます。

二分木の基本構造は以下の通りです。

具体例

入力：

出力： カウントは 2

説明： この木において、ちょうど2つの子を持つ完全ノードは「10」と「20」の2つです。それ以外のノードは、子を1つだけ持つか、まったく持っていません。

反復法（キューを使用したレベル順走査）

プログラムのアプローチ

• データ部、左ポインタ、右ポインタを持つノード構造体を定義します。
• 二分木にノードを挿入する関数を作成します。
• 完全ノードを数える関数を作成します。
• 関数内で node が NULL の場合（木が空の場合）は 0 を返します。
• 完全ノードの数を格納する一時変数 count を宣言します。
• キュー型の変数 qu を用意します。
• qu.push(node) でルートノードをキューに追加します。
• qu.empty() が false である間ループを続けます。
• Node 型の一時変数 temp を作成し、queue.front() で初期化します。
• qu.pop() で先頭要素を取り出します。
• temp->left と temp->right が両方存在する場合、count を1増やします。
• temp->left != NULL であれば qu.push(temp->left) を実行します。
• temp->right != NULL であれば qu.push(temp->right) を実行します。
• 最後に count を返し、結果を出力します。

サンプルコード

// 完全ノードを数える反復プログラム
#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int data;
    struct Node* left, *right;
};
// 二分木の完全ノードを数える関数
int fullcount(struct Node* node){
    // 木が空かどうかをチェック
    if (!node){
        return 0;
    }
    queue<Node *> myqueue;
    // レベル順走査で探索する
    int result = 0;
    myqueue.push(node);
    while (!myqueue.empty()){
        struct Node *temp = myqueue.front();
        myqueue.pop();
        if (temp->left && temp->right){
            result++;
        }
        if (temp->left != NULL){
            myqueue.push(temp->left);
        }
        if (temp->right != NULL){
            myqueue.push(temp->right);
        }
    }
    return result;
}
struct Node* newNode(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int main(void){
    struct Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(50);
    root->left->left->right = newNode(60);
    root->left->right->right = newNode(70);
    cout <<"count is: "<<fullcount(root);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

count is: 2

再帰法

プログラムのアプローチ

• データ部、左ポインタ、右ポインタを持つノード構造体を定義します。
• 二分木にノードを挿入する関数を作成します。
• 完全ノードを数える関数を作成します。
• 関数内で root が NULL の場合（木が空の場合）は 0 を返します。
• カウントを格納する一時変数 count を宣言します。
• root->left と root->right が両方存在する場合、count を1増やします。
• count = count + 左部分木の再帰呼び出し結果 + 右部分木の再帰呼び出し結果 とします。
• 最後に count を返し、結果を出力します。

サンプルコード

// 完全ノードを数える再帰プログラム
#include <iostream>
using namespace std;
struct Node{
    int data;
    struct Node* left, *right;
};
// 完全ノードの数を取得する関数
int fullcount(struct Node* root){
    if (root == NULL){
        return 0;
    }
    int result = 0;
    if (root->left && root->right){
        result++;
    }
    result += (fullcount(root->left) +
    fullcount(root->right));
    return result;
}
struct Node* newNode(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int main(){
    struct Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(50);
    root->left->left->right = newNode(60);
    root->left->right->right = newNode(70);
    cout <<"count is: "<<fullcount(root);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

count is: 2

まとめ

反復法ではキューを利用したレベル順走査（BFS）によって全ノードを巡回し、再帰法では左右の部分木に対して再帰的に関数を呼び出すことで全ノードを訪問します。どちらの手法でも計算量は O(n)、つまりノード数に比例した時間で完全ノードの総数を求めることができます。状況に応じて、スタックオーバーフローのリスクがない反復法、あるいはコードが簡潔な再帰法を選択するとよいでしょう。