C++で二分木のルートから特定のノードへのパスを出力するプログラム

このチュートリアルでは、二分木（バイナリツリー）において、ルートノードから指定されたノードまでのパスを出力するプログラムについて解説します。

すべてのノードが一意な値を持つ二分木が与えられた場合、ルートノードから特定のノードに到達するまでの完全なパスを出力することが求められます。

解き方のアプローチ

この問題は再帰を利用することで効率的に解決できます。二分木を走査しながら、目的の要素を再帰的に探索し、同時にその要素へ至る経路を記録していきます。

具体的な手順は以下のとおりです。

• 現在訪問しているノードの値を、パスを格納する配列に追加します。
• 現在のノードの値が探索対象と一致した場合は、探索成功として true を返します。
• 一致しない場合は、左部分木・右部分木の順に再帰的に同じ処理を実行します。
• どちらの部分木にも目的のノードが存在しなかった場合は、バックトラックとして現在のノードの値を配列から取り除き、false を返します。

この方法により、最終的に配列に残った値の並びが「ルートから目的ノードまでのパス」となります。

コード例

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node *left, *right;
};
struct Node* create_node(int data){
    struct Node *new_node = new Node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return new_node;
}
// ルートノードから目的の要素へのパスが存在するか判定
bool is_path(Node *root, vector<int>& arr, int x){
    if (!root)
        return false;
    arr.push_back(root->data);
    if (root->data == x)
        return true;
    if (is_path(root->left, arr, x) || is_path(root->right, arr, x))
        return true;
    arr.pop_back();
    return false;
}
// ルートノードから目的の要素までのパスを出力
void print_path(Node *root, int x){
    vector<int> arr;
    if (is_path(root, arr, x)){
        for (int i=0; i<arr.size()-1; i++)
            cout << arr[i] << " -> ";
            cout << arr[arr.size() - 1];
    }
    else
        cout << "Path doesn't exists" << endl;
}
int main(){
    struct Node *root = create_node(13);
    root->left = create_node(21);
    root->right = create_node(43);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(68);
    root->right->right = create_node(79);
    int x = 68;
    print_path(root, x);
    return 0;
}

出力

13 -> 43 -> 68

コードのポイント

このプログラムでは、まず create_node 関数で新しいノードを生成し、7つのノードからなる二分木を構築しています。探索対象の値は x = 68 です。

is_path 関数が再帰的な探索の中核であり、参照渡しのベクター arr を使って経路上のノードの値を保持します。目的のノードが見つからなかった枝については pop_back() で値を取り除くことで、正しいパスだけが残る仕組みです。

実行結果を見ると、ルートノードの 13 から右の子 43、さらにその左の子 68 へと至るパスが正しく出力されていることが確認できます。探索対象のノードが木に存在しない場合は、「Path doesn't exists」というメッセージが表示されます。