【C++】親ポインタを持つ二分木で「右の兄弟」ノードを効率的に見つける方法

この問題では、親ポインタを持つ二分木が与えられ、指定されたノードの右の兄弟(right sibling)を見つけることが課題となります。

ここでいう「右の兄弟」とは、現在のノードと同じ深さ(レベル)に存在し、かつ木全体の中で現在のノードよりも右側に位置する最初のノードのことを指します。

問題の例

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

            4
          /   \
         2     5
        /       \
       1         8
      /           \
     9             0
    /               \
   3                 7

このとき、現在のノードが 3 であれば、同じレベル(最下層)にあり右側に位置する 7 が右の兄弟となります。

入力

Node = 3

出力

7

解法のアプローチ

この問題に対する基本的な解法は、親ポインタを利用して木を上方向にたどりながらレベル数をカウントするというものです。具体的な手順は以下の通りです。

1. 現在のノードから出発し、親ノードへ移動しながらレベル数を1ずつ増やしていきます。
2. 「現在のノードが親の左の子である」という条件を満たす祖先ノードが見つかるまで上昇を続けます。これは、その祖先の右側の部分木に目的の兄弟が存在する可能性があるためです。
3. 祖先が見つかったら、その親の右の子(右部分木)へ移動します。
4. 今度は右部分木を下りながら、先ほどカウントしたレベル数だけ降ります。子ノードを選ぶ際は、まず左の子を優先し、左の子が存在しない場合のみ右の子を選びます。
5. レベル数が0になった時点のノードが、求める右の兄弟です。

もし途中で適切なノードが見つからない場合は再帰的に探索を続け、それでも見つからなければ「右の兄弟は存在しない」と判断できます。

C++による実装例

以下は、この解法を実装したC++プログラムの完全なコードです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
   Node* temp = new Node;
   temp->data = item;
   temp->left = temp->right = NULL;
   temp->parent = parent;
   return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
   if (node == NULL || node->parent == NULL)
      return NULL;
   while (node->parent->right == node ||
      (node->parent->right == NULL && node->parent->left == node)) {
         if (node->parent == NULL || node->parent->parent == NULL)
            return NULL;
      node = node->parent;
      level++;
   }
   node = node->parent->right;
   if (node == NULL)
      return NULL;
   while (level > 0) {
      if (node->left != NULL)
         node = node->left;
      else if (node->right != NULL)
         node = node->right;
      else
         break;
      level--;
   }
   if (level == 0)
      return node;
   return findRightSiblingNodeBT(node, level);
}
int main(){
   Node* root = newNode(4, NULL);
   root->left = newNode(2, root);
   root->right = newNode(5, root);
   root->left->left = newNode(1, root->left);
   root->left->left->left = newNode(9, root->left->left);
   root->left->left->left->left = newNode(3, root->left->left->left);
   root->right->right = newNode(8, root->right);
   root->right->right->right = newNode(0, root->right->right);
   root->right->right->right->right = newNode(7, root->right->right->right);
   Node * currentNode = root->left->left->left->left;
   cout<<"The current node is "<<currentNode->data<<endl;
   Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
   if (rightSibling)
      cout<<"The right sibling of the current node is "<<rightSibling->data;
   else
      cout<<"No right siblings found!";
   return 0;
}

実行結果

The current node is 3
The right sibling of the current node is 7

まとめ

このアルゴリズムは、親ポインタを活用することで木をルートから再度探索することなく、対象ノードから直接目的の兄弟へたどり着ける点が特徴です。計算量は木の高さに依存し、最悪の場合でも O(h)(h は木の高さ)程度で済むため、効率的な手法といえます。左右の高さが不揃いな二分木でも正しく動作する点もポイントです。