C++で二分木のルートから共通祖先までのパス上の共通ノードを出力する方法

この記事では、二分木とその中の2つのノードが与えられたときに、ルートから各ノードへの経路上に存在する共通ノード、すなわち両ノードの共通祖先をすべて出力する方法を解説します。

二分木とは？

二分木（Binary Tree）とは、すべてのノードが最大2つの子ノードを持つことができる特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。

祖先ノードとは？

祖先ノードとは、木構造において、より下位の階層にあるノードと接続されているノードのことを指します。

共通祖先ノードとは？

2つのノードの共通祖先ノードとは、木の中で両方のノードにとって祖先となるノードのことです。

例：

上記の二分木において、ノード0とノード6の共通祖先を求める場合を考えてみましょう。

出力： 3, 2

それでは、この問題をもとに、解決のためのアルゴリズムを作成していきましょう。

アルゴリズム

ステップ1：与えられた木の2つのノードについて、最小共通祖先（LCA）を見つけ、それを出力します。
ステップ2：ルートノードに向かって遡りながら、経路上に出てくるすべてのノードを出力します。

C++での実装例

それでは、この問題の解法を示すプログラムを作成してみましょう。

#include <iostream>
using namespace std;
struct Node {
    struct Node* left, *right;
    int key;
};
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
    if (root == NULL)
        return NULL;
    if (root->key == n1 || root->key == n2)
        return root;
    Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
    Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
    if (left_lca && right_lca)
        return root;
    return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
    if (root == NULL)
        return false;
    if (root->key == target) {
        cout << root->key << "\t";
        return true;
    }
    if (printAncestorNodes(root->left, target) ||
    printAncestorNodes(root->right, target)) {
        cout << root->key << "\t";
        return true;
    }
    return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
    struct Node* LCA = LowestCommonAncestors(root, first, second);
    if (LCA == NULL)
        return false;
    printAncestorNodes(root, LCA->key);
    return true;
}
int main(){
    Node* root = insertNode(24);
    root->left = insertNode(8);
    root->right = insertNode(69);
    root->left->left = insertNode(12);
    root->left->right = insertNode(41);
    root->right->left = insertNode(50);
    root->right->right = insertNode(3);
    root->left->left->left = insertNode(22);
    root->right->left->left = insertNode(10);
    root->right->left->right = insertNode(6);
    if (printcommonAncestors(root, 6, 3) == false)
        cout << "No Common nodes";
    return 0;
}

出力結果

69 24

プログラムの解説

このプログラムの処理の流れは以下の通りです。

まず、LowestCommonAncestors関数が再帰的に木を探索し、指定された2つのノード（この例では6と3）の最小共通祖先（LCA）を特定します。左右の子木それぞれから結果を受け取り、両側に見つかればその時点のノードがLCAとなります。

次に、printAncestorNodes関数がLCAのキー値を目標として、ルートから目標ノードまでの経路上のノードを順に出力します。この例では、ノード6と3のLCAは69であるため、「69 24」という出力が得られます。

なお、共通祖先が存在しない場合は「No Common nodes」と表示されるようになっています。