与えられた二分木が満二分木（Full Binary Tree）かどうかを判定するC++プログラム

二分木が与えられたとき、それが満二分木（Full Binary Tree）であるかどうかを判定するのが本記事のテーマです。すべてのノードが子を0個または2個持つとき、その二分木は満二分木と呼ばれます。

入力例と出力例

入力1：

出力：

1

説明： 葉ノード以外のすべてのノードが2つの子を持っているため、この二分木は満二分木です。

入力2：

出力：

0

説明： ノード2が子を1つしか持っていないため、この二分木は満二分木ではありません。

問題を解くためのアプローチ

与えられた二分木が満二分木かどうかを判定するには、左部分木と右部分木に対して再帰的にチェックを行うのが効果的です。

• ノードとその子から構成される二分木を入力として受け取ります。
• ブール型関数 isFullBinaryTree(Node* root) は根ノードを引数に取り、木が満二分木であれば true を、そうでなければ false を返します。
• 基本条件：根ノードが NULL（空）の場合は true を返します。
• 左部分木と右部分木がどちらも NULL の場合は true を返します。
• 左部分木と右部分木それぞれに対して再帰的にチェックを行い、その結果を返します。

実装例

#include<iostream>
using namespace std;
struct treenode {
    int data;
    treenode *left;
    treenode *right;
};
struct treenode *createNode(int d) {
    struct treenode *root = new treenode;
    root->data = d;
    root->left = NULL;
    root->right = NULL;
    return root;
}
bool isFullBinaryTree(struct treenode *root) {
    if (root == NULL) {
        return true;
    }
    if (root->left == NULL && root->right == NULL) {
        return true;
    } else if (root->left && root->right) {
        return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
    }
    return false;
}
int main() {
    struct treenode *root = NULL;
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(4);
    root->left->left = createNode(5);
    root->right->left = createNode(6);
    if (isFullBinaryTree(root)) {
        cout << "1" << endl;
    } else {
        cout << "0" << endl;
    }
    return 0;
}

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

出力

0

説明： この二分木では、ノード3が子を1つ（左の子のみ）しか持っていません。満二分木であるためには、すべてのノードが子を0個または2個持つ必要があるため、この木は満二分木とはみなされず、出力は0となります。

なお、このアルゴリズムは各ノードを一度ずつ訪問するため、ノード数を n とすると計算量は O(n) であり、非常に効率的です。