【C++】二分木内の任意の2つのノード間のパスを出力する方法

はじめに

本記事では、C++プログラミングにおいて二分木（バイナリツリー）内の任意の2つのノード間のパス（経路）を出力する方法を解説します。

前提として、すべてのノードが互いに異なる値を持つ二分木が与えられ、その中から指定した2つのノードをつなぐ経路を出力することを目標とします。

例として、次のような二分木を考えます。

具体例： ノード140からノード211までの経路を出力したい場合、期待される出力は以下の通りです。

Output: 140->3->10->211

解決のアプローチ

基本的なアイデアは、「ルートノードから目的の2つのノードそれぞれへの経路」を求め、それらを2つの別々のベクター（配列）である path1 と path2 に格納するというものです。

その後、以下の2つの場合に分けて処理を行います。

• 2つのノードがルートの異なる部分木に存在する場合： 片方が左部分木、もう片方が右部分木にあるケースです。この場合、ルートノードは必ずノード1からノード2への経路の途中に位置することが明らかです。したがって、path1 を逆順に出力し、続いて path2 を出力すればよいことになります。
• 2つのノードが同じ部分木に存在する場合： 両方のノードが左部分木または右部分木のどちらかに属しているケースです。この場合、ルートから2つのノードへの経路には途中に「分岐点（交差点）」が存在し、その分岐点までは両方の経路が共通しています。この交差点を見つけ、そこから先を上記の場合と同様の方法で出力します。

アルゴリズム

START
STEP 1-> 構造体 Node を定義する
    （int data と Node *left, *right を持つ）
STEP 2-> ツリー生成関数 struct Node* tree(int data) を定義する
FUNCTION bool path(Node* root, vector& arr, int x)
STEP 1-> IF root が NULL ならば
    RETURN false
    END IF
STEP 2-> arr.push_back(root->data)
    IF root->data == x THEN
       RETURN true
    END IF
STEP 3-> IF path(root->left, arr, x) || path(root->right, arr, x) THEN
    RETURN true
STEP 4-> arr.pop_back()
    return false
END FUNCTION
FUNCTION void printPath(Node* root, int n1, int n2)
STEP 1-> vector<int> path1 を定義する
STEP 2-> vector<int> path2 を定義する
STEP 3-> 関数 path(root, path1, n1) を呼び出す
STEP 4-> 関数 path(root, path2, n2) を呼び出す
STEP 5-> intersection = -1、i = 0、j = 0 を設定する
STEP 6-> WHILE i != path1.size() || j != path2.size() の間ループ
    IF i == j && path1[i] == path2[j]
       i を 1 増やす
       j を 1 増やす
    ELSE
       intersection = j - 1 と設定して BREAK
    END IF
END WHILE
STEP 7-> FOR i = path1.size() - 1 から i > intersection の間 i-- しながら
    PRINT path1[i]
    END FOR
STEP 8-> FOR i = intersection から i < path2.size() の間 i++ しながら
    PRINT path2[i]
END FOR

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 二分木のノード構造体
struct Node {
    int data;
    Node *left, *right;
};
struct Node* tree(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
bool path(Node* root, vector<int>& arr, int x){
    if (!root)
        return false;
    // ノードの値を 'arr' に追加する
    arr.push_back(root->data);
    // 目的のノードであれば true を返す
    if (root->data == x)
        return true;
    if (path(root->left, arr, x) || path(root->right, arr, x))
        return true;
    arr.pop_back();
    return false;
}
// 二分木内の任意の2つのノード間の
// パスを出力する関数
void printPath(Node* root, int n1, int n2){
    // 経路を格納するベクター
    vector<int> path1;
    vector<int> path2;
    path(root, path1, n1);
    path(root, path2, n2);
    int intersection = -1;
    int i = 0, j = 0;
    while (i != path1.size() || j != path2.size()) {
        if (i == j && path1[i] == path2[j]) {
            i++;
            j++;
        } else {
            intersection = j - 1;
            break;
        }
    }
    // 必要な経路を出力する
    for (int i = path1.size() - 1; i > intersection; i--)
        cout << path1[i] << " ";
    for (int i = intersection; i < path2.size(); i++)
        cout << path2[i] << " ";
}
int main(){
    // 二分木の構築
    struct Node* root = tree(1);
    root->left = tree(2);
    root->left->left = tree(4);
    root->left->left->left = tree(6);
    root->left->right = tree(5);
    root->left->right->left = tree(7);
    root->left->right->right = tree(8);
    root->right = tree(3);
    root->right->left = tree(9);
    root->right->right = tree(10);
    int node1 = 5;
    int node2 = 9;
    printPath(root, node1, node2);
    return 0;
}

出力結果

このプログラムを実行すると、次の出力が得られます。

5 2 1 3 9

まとめ

このように、ルートから各ノードへの経路を再帰的に求め、2つの経路の共通部分（交差点）を特定することで、二分木内の任意の2つのノード間のパスを出力できます。各ノードを高々一度ずつ訪問するため、計算量は O(n) となり、効率的かつ実用的な手法といえます。