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

はじめに

本記事では、二分木（バイナリツリー）が与えられたとき、指定したノードの祖先（ancestor）となるすべてのノードを出力する方法を解説します。

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

以下は二分木の一例です。

祖先ノードとは

二分木におけるあるノードの祖先とは、そのノードより上位の階層に位置し、根からそのノードへの経路上にあるノードを指します。

例として、次の図を見てみましょう。

この二分木において、値が 3 のノードの祖先は 8 とその上位のノードです。

アルゴリズムの考え方

この問題を解くには、根ノードから目的のノードへ向かって順に辿る方法を用います。具体的には次の手順です。

1. 根ノードから再帰的に探索を開始します。
2. 現在のノードがNULLなら false を返します。
3. 現在のノードの値が目的の値と一致すれば true を返します。
4. 左部分木または右部分木のいずれかに目的ノードが見つかった場合、現在のノードは祖先にあたるため、その値を出力して true を返します。

この処理により、根から目的ノードまでの経路上にあるすべてのノードが出力されます。

C++での実装例

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
};
bool AncestorsNodes(struct node *root, int target){
    if (root == NULL)
        return false;
    if (root->data == target)
        return true;
    if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ){
        cout << root->data << " ";
        return true;
    }
    return false;
}
struct node* insertNode(int data){
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}
int main(){
    struct node *root = insertNode(10);
    root->left = insertNode(6);
    root->right = insertNode(13);
    root->left->left = insertNode(3);
    root->left->right = insertNode(8);
    root->right->left = insertNode(12);
    cout<<"Ancestor Nodes are ";
    AncestorsNodes(root, 8);
    getchar();
    return 0;
}

実行結果

Ancestor Nodes are 6 10

コードの解説

上記のプログラムでは、まず insertNode 関数で新しいノードを作成し、二分木を構築しています。AncestorsNodes 関数は再帰的に呼び出され、目的のノードが見つかった経路上のノード（祖先）を後ろから順に出力します。

この例では値 8 のノードを探索しており、その祖先である 6 と 10 が出力されます。探索対象のノードが存在しない場合、何も出力されません。

計算量

• 時間計算量： 最悪の場合、木全体を走査するため O(n) となります（n はノード数）。
• 空間計算量： 再帰呼び出しによるスタック領域として、木の高さに比例した O(h) が必要です。

まとめ

二分木における特定ノードの祖先を出力するには、根から目的ノードへの経路を再帰的に探索し、経路上のノードを出力するのがシンプルかつ効率的な方法です。再帰を使った実装はコードも簡潔になり、木構造の問題全般に応用できる重要なテクニックです。