C++で二分木のすべての完全ノード（フルノード）を出力する方法

この記事では、二分木が与えられたときに、その木に含まれるすべての完全ノード（フルノード）を見つけて出力する方法を解説します。

二分木と完全ノードとは？

二分木（バイナリツリー）とは、各ノードが最大2つの子ノードを持つことができる木構造のことです。子ノードは0個（葉）、1個、または2個のいずれかになります。

完全ノード（フルノード）とは、左の子と右の子の両方を持っているノードのことを指します。言い換えれば、左右どちらか一方しか子を持たないノードや、子をまったく持たないノードは完全ノードではありません。

具体例

次のような二分木を考えてみましょう。

        100
       /   \
     56     12
    /      /  \
  89      32    45

この場合、左と右の両方の子を持つノードは 100 と 12 の2つです。したがって、出力結果は次のようになります。

出力： 100 12

解決アプローチ

この問題は非常にシンプルな方法で解くことができます。手順は以下の通りです。

1. 任意の走査アルゴリズム（ここでは中順走査：inorder traversal）を使って木を巡回します。
2. 現在のノードが左の子と右の子の両方を持っているかどうかを確認します。
3. 両方の子を持っている場合は、そのノードの値を出力します。持っていない場合は何もしません。

この処理を再帰的に行うことで、木の中のすべての完全ノードを効率よく見つけることができます。

C++による実装例

以下は、上記のアプローチを実装したC++プログラムです。

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

// 新しいノードを作成する関数
Node* insertNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// 完全ノードを出力する関数（中順走査）
void printFullNode(Node* root) {
    if (root != NULL) {
        printFullNode(root->left);
        if (root->left != NULL && root->right != NULL)
            cout << root->data << "\t";
        printFullNode(root->right);
    }
}

int main() {
    Node* root = insertNode(100);
    root->left = insertNode(56);
    root->right = insertNode(12);
    root->left->left = insertNode(89);
    root->right->left = insertNode(32);
    root->right->right = insertNode(45);

    cout << "木のすべての完全ノード :\n";
    printFullNode(root);
    return 0;
}

実行結果

木のすべての完全ノード :
100    12

計算量について

このアルゴリズムは木のすべてのノードを一度だけ訪問するため、時間計算量は O(n)（nはノード数）となります。また、再帰呼び出しによるスタック領域が必要で、空間計算量は木の高さに依存し、最悪の場合（偏った木）で O(n)、バランスの取れた木では O(log n) となります。