C++で二分木の前順走査における先行ノード（Preorder Predecessor）を求める方法

問題の概要

この問題では、二分木とあるノードの値が与えられ、そのノードの前順走査における先行ノード（Preorder Predecessor）を出力することが求められます。

用語の整理

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

前順走査（Preorder Traversal）は、木のノードを巡回する方法の一つで、「根ノード → 左の子 → 右の子」の順に訪問していきます。

前順先行ノードとは、前順走査において対象ノードの直前に訪問されるノードのことを指します。

具体例

次の例で問題を確認してみましょう。

入力: 1
出力: 9

この例では、値「1」のノードの直前に訪問されるノードは「9」であるため、出力は9となります。

解法アプローチ

1. 素朴な方法（ナイーブな手法）

最も単純な方法は、二分木全体の前順走査を実際に行い、与えられたノードの直前に現れる要素を出力することです。しかし、この方法は毎回木全体を走査する必要があり、計算量がO(n)となるため効率が良いとは言えません。

2. 効率的な方法（ノードの位置関係を利用）

より効果的な解法は、対象ノードの位置関係に着目し、そこから直接先行ノードを導き出すものです。各親ノードへのポインタ（parent）を持たせておくことで、以下のルールで判定できます。

• ノードが根ノードの場合：先行ノードは存在しないため、NULLを返します。
• ノードが親の左の子である場合、または親に左の子が存在しない場合：前順走査では親の直後に左の子（または右の子）が訪問されるため、親ノードが先行ノードとなります。
• ノードが右の子であり、親に左の子が存在する場合：親の左部分木がすべて先に走査されるため、その左部分木内で最後に訪問されるノード（右の子をたどれる限りたどり続けた先のノード）が先行ノードとなります。

この方法では、木全体を走査する必要がなく、対象ノードから親や兄弟のポインタをたどるだけで答えが求まります。

C++での実装例

#include <iostream>
using namespace std;
struct Node {
    struct Node *left, *right, *parent;
    int key;
};
struct Node* insertNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = temp->parent = NULL;
    temp->key = key;
    return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
    if (n == root)
        return NULL;
    Node* parent = n->parent;
    if (parent->left == NULL || parent->left == n)
        return parent;
    Node* curr = parent->left;
    while (curr->right != NULL)
        curr = curr->right;
    return curr;
}
int main() {
    Node* root = insertNode(99);
    root->parent = NULL;
    root->left = insertNode(4);
    root->left->parent = root;
    root->left->left = insertNode(18);
    root->left->left->parent = root->left;
    root->left->right = insertNode(50);
    root->left->right->parent = root->left;
    root->right = insertNode(26);
    root->right->parent = root;
    root->right->left = insertNode(5);
    root->right->left->parent = root->right;
    root->right->right = insertNode(10);
    root->right->right->parent = root->right;
    Node* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
    if (preOrderPredecessor)
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
    else
        cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
    return 0;
}

実行結果

Preorder Predecessor of 50 is 18

この例では、ノード「50」は親「4」の右の子であり、親には左の子「18」が存在します。したがって、左部分木内で最後に訪問されるノード、つまり「18」が50の前順先行ノードとなります。

まとめ

二分木の前順先行ノードを求める問題は、各ノードに親ポインタを持たせることで、木全体を走査することなく効率的に解くことができます。ノードが根か、左の子か、右の子かという位置関係を判定するだけでよく、実用的で分かりやすいアルゴリズムです。