C++で二分木のノードの後順走査における後続ノード（サクセサ）を求める方法

この問題では、二分木とあるノードが与えられ、そのノードの後順走査（ポストオーダー）における後続ノードを出力することが求められます。

二分木とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造のことです。

後順走査は木の巡回手法の一つで、まず左部分木を巡回し、次に右部分木を巡回し、最後に根（ルート）を訪問します。

上図の木を後順走査すると、8 4 2 7 9 6 の順になります。

具体例で問題を理解しよう

• 入力：上図の二分木、対象ノード = 7
• 出力：9
• 説明：後順走査の順序「8 4 2 7 9 6」を見ると、7 の直後に訪問されるのは 9 であることがわかります。

シンプルな解法

最も簡単なアプローチは、木全体の後順走査をあらかじめ求めておき、対象ノードの隣の値を出力するというものです。しかし、これでは非効率なため、より優れた解法を考えましょう。

効率的な解法

効率的な解法は、後順走査の性質に関する以下の一般的な観察に基づいています。

• 根（ルート）は後順走査で最後に訪問されるため、その後続ノードは NULL となります。
• 現在のノードが右の子である場合、親ノードが後続ノードになります。
• 現在のノードが左の子である場合：
  • 右の兄弟が存在しなければ、親ノードが後続ノードになります。
  • 右の兄弟が存在すれば、その兄弟ノード、またはその部分木の最も左のノードが後続ノードになります。

この方法は非常に効率的で、計算量は O(h)（h は木の高さ）に抑えられます。

C++による実装例

以下は、上記の解法を実装したプログラムです。

#include <iostream>
using namespace std;
struct Node {
    struct Node *left, *right, *parent;
    int value;
};
struct Node* insertNode(int value) {
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->value = value;
    return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
    if (n == root)
       return NULL;
    Node* parent = n->parent;
    if (parent->right == NULL || parent->right == n)
       return parent;
    Node* curr = parent->right;
    while (curr->left != NULL)
       curr = curr->left;
    return curr;
}
int main(){
    struct Node* root = insertNode(6);
    root->parent = NULL;
    root->left = insertNode(2);
    root->left->parent = root;
    root->left->left = insertNode(8);
    root->left->left->parent = root->left;
    root->left->right = insertNode(4);
    root->left->right->parent = root->left;
    root->right = insertNode(9);
    root->right->parent = root;
    root->right->left = insertNode(7);
    root->right->left->parent = root->right;
    root->left->right->left = insertNode(14);
    struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
    if (successorNode)
       cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
    else
       cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
    return 0;
}

実行結果

Postorder successor of 4 is 2

このプログラムでは、ノード 4 に対して後続ノードを求めています。ノード 4 は左子であり、かつ親（ノード 2）には右子が存在しないため、後続ノードは親であるノード 2 となり、正しく出力されていることが確認できます。