C++で二分木内の指定キーの次の右ノードを検索する方法

問題概要

この問題では、二分木（Binary Tree）とキー値が与えられます。目的は、指定されたキーを持つノードの次の右ノードを見つけることです。

二分木とは、各ノードが最大2つの子ノード（左の子と右の子）を持つ特殊なデータ構造で、データの格納や効率的な探索に広く活用されています。

具体例で理解しよう

入力

key = 4

出力

5

説明

ノード4と同じレベルに位置し、その右隣にある要素は5です。したがって、答えは5となります。

解決アプローチ

この問題に対するシンプルな解決策は、幅優先探索（レベル順走査）を用いて二分木を走査することです。

具体的には、以下の手順で処理を行います。

1. キューを使用してレベル順にノードを走査します。
2. 指定されたキー値を持つノードが見つかったら、走査順序上で同じレベルに次のノードが存在するかどうかを確認します。
3. 次のノードが存在すればそれを返し、存在しない場合（キーが最右端のノードである場合など）はNULLを返します。

このアルゴリズムでは、ノードとそのレベル情報をそれぞれ別のキューで管理することで、同じレベル内での隣接関係を簡単に判定できます。

実装例

以下は、この解決策の動作を示すC++プログラムです。

#include <iostream>
#include <queue>
using namespace std;
struct node {
    struct node *left, *right;
    int key;
};
node* newNode(int key) {
    node *temp = new node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
node* findNextRightNodeBT(node *root, int k) {
    if (root == NULL)
        return 0;
    queue<node *> nodeVal;
    queue<int> nodeLevel;
    int level = 0;
    nodeVal.push(root);
    nodeLevel.push(level);
    while (nodeVal.size()) {
        node *node = nodeVal.front();
        level = nodeLevel.front();
        nodeVal.pop();
        nodeLevel.pop();
        if (node->key == k) {
            if (nodeLevel.size() == 0 || nodeLevel.front() != level)
                return NULL;
            return nodeVal.front();
        }  
        if (node->left != NULL) {
            nodeVal.push(node->left);
            nodeLevel.push(level+1);
        }
        if (node->right != NULL) {
            nodeVal.push(node->right);
            nodeLevel.push(level+1);
        }
    }
    return NULL;
}
int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    int key = 4;
    cout<<"The next right node of the node "<<key<<" is ";
    node *nextNode = findNextRightNodeBT(root, key);
    if(nextNode != NULL)
        cout<<nextNode->key;
    else
        cout<<"not available";
    return 0;
}

出力

The next right node of the node 4 is 5

まとめ

この記事では、二分木において指定されたキーを持つノードの次の右ノードを検索する方法を解説しました。幅優先探索とキューを組み合わせることで、時間計算量O(N)、空間計算量O(N)で効率的に解くことができます。キーがそのレベルの最右端にある場合は、次の右ノードが存在しないためNULLが返される点にも注意しましょう。