C++で二分木の根から葉への最短経路を出力する方法｜BFS（幅優先探索）による実装

問題の概要

二分木が与えられたとき、根（ルート）から葉（リーフ）に至る複数の経路の中から、最も短い経路を見つけ出して出力するプログラムを作成します。

木は左から右へと走査するため、同じ深さの最短経路が複数存在する場合は、左側にある最初に走査された最短経路を出力します。

この問題は、キュー（queue）を使ったレベル順走査（幅優先探索・BFS）で各レベルを順にたどることで解くことができます。BFSは浅い階層から順に探索を進めるため、最初に見つかった葉への経路が、すなわち根から葉への最短経路となります。

上図の二分木では、根から葉への経路として以下のものが考えられます。

10 -> 3（すべての経路の中で最短）
10 -> 211 -> 100
10 -> 211 -> 146

入力例と出力例

入力 : 10 3 211 100 146
出力 : 10 3

アルゴリズム

ステップ1：ノード構造体の作成

struct node
    struct node *left, *right
    int data
End

ステップ2：ノードを生成する関数

node* newnode(int data)
    node *temp = new node
    temp->data = data
    temp->left = temp->right = NULL
    return temp

ステップ3：経路を計算する関数

親ノードの情報を格納したマップ（prnt）を再帰的にたどり、根に向かって経路を出力します。

void path(int data, unordered_map <int,int> prnt)
    IF prnt[data] == data
        Return
    End
    path(prnt[data], prnt)
    print prnt[data]

ステップ4：左側の最短経路を求める関数

キューを使ったレベル順走査を行い、最初に見つかった葉と、そこまでの親子関係をマップに記録します。

void left(Node* root)
    STLのqueue<Node*> que を作成
    que.push(root)
    int leaf = -1
    Node* temp = NULL
    STLのunordered_map<int, int> prnt を作成
    prnt[root->data] = root->data
    While !que.empty() の間ループ
        temp = que.front()
        que.pop()
        IF !temp->left && !temp->right
            leaf = temp->data
            break
        Else
            IF temp->left
                que.push(temp->left)
                prnt[temp->left->data] = temp->data
            End
            IF temp->right
                que.push(temp->right)
                prnt[temp->right->data] = temp->data
            End
        End
    End
    path(leaf, prnt)
    print leaf

ステップ5：main() 関数内の処理

Node* root = newnode(90) で木を作成
root->left = newnode(21)
left(root) を呼び出す
終了

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体
struct Node {
    struct Node *left,*right;
    int data;
};
// 新しいノードを作成する関数
Node* newnode(int data){
    Node* temp = new Node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
// 経路を出力する関数
void path(int data, unordered_map <int,int> prnt) {
    if (prnt[data] == data)
        return;
    path(prnt[data], prnt);
    cout << prnt[data] << " ";
}
// 葉への最短経路を求める関数
void left(Node* root) {
    queue<Node*> que;
    que.push(root);
    int leaf = -1;
    Node* temp = NULL;
    unordered_map<int, int> prnt;
    prnt[root->data] = root->data;
    while (!que.empty()){
        temp = que.front();
        que.pop();
        if (!temp->left && !temp->right) {
            leaf = temp->data;
            break;
        } else {
            if (temp->left){
                que.push(temp->left);
                prnt[temp->left->data] = temp->data;
            }
            if (temp->right){
                que.push(temp->right);
                prnt[temp->right->data] = temp->data;
            }
        }
    }
    path(leaf, prnt);
    cout << leaf << " ";
}
int main(){
    Node* root = newnode(90);
    root->left = newnode(21);
    root->right = newnode(32);
    root->left->left = newnode(45);
    root->right->left = newnode(52);
    root->right->right = newnode(27);
    root->left->left->left = newnode(109);
    root->left->left->right = newnode(101);
    root->right->right->left = newnode(78);
    left(root);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

90 32 52

処理の解説

この例では、ノード「90」を根とする二分木に対して幅優先探索を行っています。探索はレベル順に進み、最初に到達した葉は「52」です。親情報を記録したマップをたどることで、経路「90 → 32 → 52」が正しい順序で出力されます。

BFSは浅い階層から順にノードを訪問する性質を持つため、「最初に見つかった葉までの経路＝最短経路」という保証があります。これにより、全経路を列挙して比較する必要がなく、効率的に最短経路を求められるのが大きな利点です。