C++で二分木のすべての内部ノードを出力する方法

この記事では、与えられた二分木からすべての内部ノードを見つけて出力する方法を解説します。

二分木と内部ノードとは

二分木（バイナリツリー）とは、各ノードが最大2つの子ノードを持つことができる木構造のデータ構造です。ノードは子をまったく持たないこともあれば、1つだけ持つこと、2つ持つこともあります。

内部ノードとは、少なくとも1つの子ノードを持つノードのことを指します。言い換えると、葉ノード（子を持たないノード）以外のノードがすべて内部ノードです。

具体例

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

この木の場合、子ノードを持っているのは 7、4、9 の3つのノードなので、出力は以下のようになります。

出力： 7 4 9

解決アプローチ：BFS（幅優先探索）

この問題は、BFS（幅優先探索）を使って二分木を走査することで解けます。手順は以下の通りです。

• ルートノードをキューに追加します。
• キューからノードを1つずつ取り出します。
• 取り出したノードが子ノードを少なくとも1つ持っている場合（＝内部ノードの場合）、その値を出力します。
• 存在する子ノードをすべてキューに追加し、キューが空になるまでこの処理を繰り返します。

C++での実装例

上記のロジックを実装したコードがこちらです。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int data){
        left = right = NULL;
        this->data = data;
    }
};

void printNonLeafNodes(Node* root) {
    queue<Node*> treeNodes;
    treeNodes.push(root);
    while (!treeNodes.empty()) {
        Node* curr = treeNodes.front();
        treeNodes.pop();
        bool isInternal = 0;
        if (curr->left) {
            isInternal = 1;
            treeNodes.push(curr->left);
        }
        if (curr->right) {
            isInternal = 1;
            treeNodes.push(curr->right);
        }
        if (isInternal)
            cout<<curr->data<<"\t";
    }
}

int main() {
    Node* root = new Node(43);
    root->left = new Node(12);
    root->right = new Node(78);
    root->left->left = new Node(4);
    root->right->left = new Node(9);
    root->right->right = new Node(1);
    root->right->right->right = new Node(50);
    root->right->right->left = new Node(25);
    cout<<"All internal Nodes of the binary tree are :\n";
    printNonLeafNodes(root);
    return 0;
}

コードのポイント

• Node 構造体で、ノードの値と左右の子へのポインタを保持します。
• printNonLeafNodes 関数では、キューを使ってBFS走査を行い、isInternal フラグによってそのノードが内部ノードかどうかを判定しています。
• 左の子または右の子が存在すればフラグを立てて値を出力し、同時にその子をキューへ追加して走査を続けます。

実行結果

All internal Nodes of the binary tree are −
43 12 78 1

このサンプルツリーでは、43・12・78・1 の4つのノードが子を持っているため、これらが出力されます。計算量は各ノードを一度ずつ訪問するため O(n)、空間計算量も最悪ケースで O(n) となります。