C++で木の全ノードに中間順後続ノード（Inorder Successor）を設定する方法

この問題では、nextポインタを持つ木構造が与えられます。私たちのタスクは、このnextポインタに各ノードの中間順後続ノード（inorder successor）を設定することです。

まず、使用するノード構造体は以下のように定義されています。

struct node {
    int value;
    struct node* left;
    struct node* right;
    struct node* next;
}

すべてのnextポインタは初期状態でNULLに設定されており、これを各ノードの中間順後続ノードを指すように書き換える必要があります。

基本概念のおさらい

中間順走査（Inorder Traversal）とは

中間順走査は、二分木を以下の順序で訪問する走査方法です。

左の子ノード → 根ノード → 右の子ノード

中間順後続ノード（Inorder Successor）とは

中間順後続ノードとは、木の中間順走査を行ったときに、現在のノードの直後に現れるノードのことです。

具体例で理解する

以下の例を見てみましょう。

この木の中間順走査の結果は次のとおりです。

7 → 8 → 3 → 5 → 9 → 1

したがって、各ノードのnextポインタは以下のように設定されます。

5 の next は 9
8 の next は 3
7 の next は 8
3 の next は 5
9 の next は 1

解法のアプローチ

この問題を解くためには、木を逆の中間順（右→根→左）で走査します。こうすることで、各ノードを訪問した時点で、その直前に訪問したノードが「中間順後続ノード」となります。つまり、直前に訪問したノードへの参照を保持しておき、それを現在のノードのnextに代入していきます。

実装例

上記の解法を実装したC++プログラムは以下のとおりです。

#include<iostream>
using namespace std;
struct node {
    int data;
    node *left;
    node *right;
    node *next;
};
node* insertNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    Node->next = NULL;
    return(Node);
}
void populateTree(node* pop){
    static node *next = NULL;
    if (pop){
        populateTree(pop->right);
        pop->next = next;
        next = pop;
        populateTree(pop->left);
    }
}
void printNext(node * root) {
    node *ptr = root->left->left;
    while(ptr){
        cout<<"Next of "<<ptr->data<<" is ";
        cout<<(ptr->next? ptr->next->data: -1)<<endl;
        ptr = ptr->next;
    }
}
int main() {
    node *root = insertNode(15);
    root->left = insertNode(99);
    root->right = insertNode(1);
    root->left->left = insertNode(76);
    root->left->right = insertNode(31);
    cout<<"Populating the Tree by adding inorder successor to the next\n";
    populateTree(root);
    printNext(root);
    return 0;
}

実行結果

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

Populating the Tree by adding inorder successor to the next
Next of 76 is 99
Next of 99 is 31
Next of 31 is 15
Next of 15 is 1
Next of 1 is -1

まとめ

この解法では、再帰的に木を右→根→左の順で走査し、静的変数で直前に訪問したノードを追跡することで、すべてのノードの中間順後続ノードを効率的に設定できます。計算量は木のノード数をNとするとO(N)、再帰によるスタック使用のため空間計算量も最悪ケースでO(N)となります。最後のノード（中間順走査で最後に訪れるノード）には後続が存在しないため、そのnextはNULLのまま残る点にも注意してください。