C++で二分木の半ノード（ハーフノード）を数える方法【反復・再帰の両アプローチ】

本記事では、二分木（バイナリツリー）に含まれる「半ノード（ハーフノード）」の数を、反復処理と再帰処理の2つのアプローチで求める方法を解説します。

半ノードとは？

半ノードとは、子を1つだけ持ち、もう片方の子がNULL（空）になっているノードのことです。なお、子をまったく持たない葉ノードは半ノードには含まれない点に注意してください。

二分木はデータの格納に使われる特殊なデータ構造です。各ノードが最大2つの子を持つという制約があり、ソート済み配列並みの高速な検索と、連結リスト並みの高速な挿入・削除の両方を実現できるというメリットがあります。

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

具体例

入力：

出力： カウントは 2

解説： この二分木では、40 と 50 の2つのノードが子をちょうど1つだけ持つ半ノードです。それ以外のノードは、子を2つ持つか、まったく持たないかのどちらかです。

反復処理（キューを使ったレベル順走査）による実装

プログラムの考え方

• データ部と左右ポインタを持つノード構造体を定義します。
• 二分木にノードを挿入する関数を作成します。
• 半ノードをカウントする関数を作成します。
• 関数内で、まず !node（木が空）の場合は 0 を返します。
• 半ノードの個数を保持する一時変数 count を宣言します。
• キュー型の変数 qu を用意します。
• qu.push(node) でルートノードをキューに追加します。
• qu.empty() が false の間、ループを回します。
• Node 型の一時変数 temp を queue.front() で初期化します。
• qu.pop() で要素を取り出します。
• (!temp->left && temp->right) || (temp->left && !temp->right) の条件を満たせば、count を1増やします。
• temp->left が NULL でなければ qu.push(temp->left) を実行します。
• 最後に count を返し、結果を出力します。

サンプルコード

// 二分木の半ノードを数えるプログラム（反復版）
#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int data;
    struct Node* left, *right;
};
// 半ノードの個数を取得する関数
int halfcount(struct Node* node){
    // 木が空の場合
    if (!node)
    return 0;
    int result = 0; // 半ノードのカウントを初期化
    // ルートからレベル順走査（BFS）を行う
    queue<Node *> myqueue;
    myqueue.push(node);
    while (!myqueue.empty()){
        struct Node *temp = myqueue.front();
        myqueue.pop();
        if ((!temp->left && temp->right) || (temp->left && !temp->right)){
            result++;
        }
        if (temp->left != NULL){
            myqueue.push(temp->left);
        }
        if (temp->right != NULL){
            myqueue.push(temp->right);
        }
    }
    return result;
}
/* 指定されたデータを持ち、左右ポインタがNULLの新規ノードを確保する */
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: "<<halfcount(root);
    return 0;
}

実行結果

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

count is: 2

再帰処理による実装

プログラムの考え方

• データ部と左右ポインタを持つノード構造体を定義します。
• 二分木にノードを挿入する関数を作成します。
• 半ノードをカウントする関数を作成します。
• 関数内で、root == NULL の場合は 0 を返します。
• 半ノードの個数を保持する一時変数 count を宣言します。
• (root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL) の条件を満たせば、count を1増やします。
• count = count + 左部分木の再帰呼び出し + 右部分木の再帰呼び出し とします。
• 最後に count を返し、結果を出力します。

サンプルコード

// 二分木の半ノードを数えるプログラム（再帰版）
#include <bits/stdc++.h>
using namespace std;
// 二分木のノードはデータ、左の子へのポインタ、右の子へのポインタを持つ
struct Node{
    int data;
    struct Node* left, *right;
};
int halfcount(struct Node* root){
    if (root == NULL)
    return 0;
    int result = 0;
    if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right ==
    NULL)){
        result++;
    }
    result += (halfcount(root->left) + halfcount(root->right));
    return result;
}
/* 指定されたデータを持ち、左右ポインタがNULLの新規ノードを確保する */
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: "<<halfcount(root);
    return 0;
}

実行結果

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

count is: 2

まとめ

どちらのアプローチでも同じ結果が得られます。反復法はキューを使った幅優先探索（BFS）で木全体を走査するため、深い木でもスタックオーバーフローの心配が少なく、再帰法はコードが簡潔で直感的に理解しやすいという特徴があります。それぞれの手法の計算量はいずれも O(n)、必要な領域は反復法ではキューのサイズ（最悪 O(n)）、再帰法では呼び出しスタックの深さ（最悪 O(n)）となります。