C++で二分木の非葉ノード（葉以外のノード）を数える方法

二分木が与えられ、その中に存在する非葉ノード（葉以外のノード）の数を求めるのが課題です。

二分木とは

二分木（バイナリツリー）は、データを格納するために使われる特殊なデータ構造です。各ノードが最大2つの子ノードしか持てないという特別な条件を持っています。二分木は、整列配列のような高速な検索性能と、連結リストのような高速な挿入・削除性能の両方の利点を兼ね備えています。

ここで数える「非葉ノード」とは、子ノードを1つ以上持つノードのことで、親ノードとも呼ばれます。

二分木の構造は以下のようになります。

具体例

入力 −

出力 − 非葉ノードの数：3

説明 − この木では、27・14・35 の3つのノードが子を持っているため、これらが非葉ノードとしてカウントされます。

アルゴリズムのアプローチ

• 左の子ノードへのポインタ、右の子ノードへのポインタ、そしてデータ部を持つ二分木のノード構造体を定義します。
• 呼び出されるたびに新しいノードを挿入する関数を作成します。新しいノードにデータを格納し、左右のポインタを NULL に設定して、そのノードを返します。
• 二分木内の非葉ノードの数を数える再帰関数を作成します。
  • ルートが NULL、またはルートの左右の子がどちらも NULL の場合は 0 を返します。
  • それ以外の場合は、「1 + 左部分木に対する再帰呼び出し + 右部分木に対する再帰呼び出し」を返します。
• 最後にカウント結果を出力します。

C++での実装例

#include <iostream>
using namespace std;
// ノードの構造体
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
// 新しいノードを生成する関数
struct Node* newNode(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
// 非葉ノードを数える関数
int nonleaf(struct Node* root){
    if (root == NULL || (root->left == NULL && root->right == NULL)){
        return 0;
    }
    return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// メイン関数
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(21);
    root->right = newNode(33);
    root->left->left = newNode(48);
    root->left->right = newNode(51);
    cout << "count of non-leaf nodes is: " << nonleaf(root);
    return 0;
}

実行結果

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

count of non-leaf nodes is: 2

この例では、10・21・33 のうち子を持つノードがカウントされ、正しく非葉ノードの数が出力されていることがわかります。この再帰的なアプローチを使えば、任意の規模の二分木に対して効率的に非葉ノードを数えることができます。