C++で再帰を使わずに二分木の特定ノードの祖先を出力する方法

問題の概要

この問題では、二分木が与えられ、指定したノードの祖先（ancestor）となるノードをすべて出力することが求められます。

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

祖先ノードとは

二分木におけるあるノードの祖先とは、そのノードより上位のレベルに位置するノードのことを指します。

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

この二分木において、値が 17 のノードの祖先は、27 → 25 → 15 となります。

解法のアプローチ

この問題を解くには、ルートノードからターゲットノードへ向かって、二分木を一段ずつ下方向に探索していきます。そして、その経路上にあるノードをすべて出力します。

通常、この種の処理は再帰呼び出しを用いて実装されますが、今回は再帰を使わない反復処理（イテレーティブな探索）で実装します。そのために、スタックを使用してターゲットノードの祖先を格納します。

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

• 二分木を後順走査（postorder traversal）で探索します。
• 探索の過程で通過したノードをスタックに格納していきます。
• ターゲットノードが見つかった時点で、スタックに残っているノードがすべて祖先となります。
• 最後にスタックの内容を取り出して出力します。

実装例（C++）

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Node{
    int data;
    struct Node *left, *right;
};

struct Stack{
    int size;
    int top;
    struct Node* *array;
};

struct Node* insertNode(int data){
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Stack* createStack(int size){
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
    return stack;
}

int isFull(struct Stack* stack){
    return ((stack->top + 1) == stack->size);
}

int isEmpty(struct Stack* stack){
    return stack->top == -1;
}

void push(struct Stack* stack, struct Node* node){
    if (isFull(stack))
        return;
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack){
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}

struct Node* peek(struct Stack* stack){
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top];
}

void AncestorNodes(struct Node *root, int key){
    if (root == NULL) return;
    struct Stack* stack = createStack(MAX_SIZE);
    while (1){
        while (root && root->data != key){
            push(stack, root);
            root = root->left;
        }
        if (root && root->data == key)
            break;
        if (peek(stack)->right == NULL){
            root = pop(stack);
            while (!isEmpty(stack) && peek(stack)->right == root)
                root = pop(stack);
        }
        root = isEmpty(stack)? NULL: peek(stack)->right;
    }
    while (!isEmpty(stack))
        printf("%d ", pop(stack)->data);
}

int main(){
    struct Node* root = insertNode(15);
    root->left = insertNode(10);
    root->right = insertNode(25);
    root->left->left = insertNode(5);
    root->left->right = insertNode(12);
    root->right->left = insertNode(20);
    root->right->right = insertNode(27);
    root->left->left->left = insertNode(1);
    root->left->right->right = insertNode(14);
    root->right->right->left = insertNode(17);
    printf("The ancestors of the given node are : ");
    AncestorNodes(root, 17);
    getchar();
    return 0;
}

実行結果

The ancestors of the given node are : 27 25 15

処理の流れの解説

上記のプログラムでは、以下のような流れで処理が行われます。

1. ルートノードから開始し、左側の子ノードを順にたどりながら、通過したノードをスタックにプッシュしていきます。
2. 左側をたどりきってもターゲットノードが見つからない場合は、スタックの先頭ノードを確認し、右の子を持たないノードをポップして戻ります。
3. 右側の部分木に移動して探索を続けます。
4. ターゲットノード（この例では値 17）が見つかった時点でループを抜けます。
5. この時点でスタックに残っているノードが、ターゲットノードの祖先そのものです。順にポップしながら出力します。

この方法により、再帰呼び出しを使わずに、スタックベースの反復処理だけでノードの祖先を効率的に求めることができます。深い木構造を扱う場合でも、スタックのサイズを適切に設定することで安全に動作させることが可能です。