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

この問題では、二分木とあるノードの値が与えられ、そのノードの前順走査(プレオーダー)における後続ノードを出力することが求められます。

基本用語の整理

二分木(Binary Tree):各ノードが最大2つの子ノードを持つことができる特別な木構造です。

前順走査(Preorder Traversal):木のノードを巡回する方法の1つで、「根ノード → 左の子 → 右の子」の順に訪問します。

前順走査における後続ノード:前順走査の順序において、対象ノードの直後に現れるノードのことです。

問題例

具体例を見て、問題を理解しましょう。

入力: 9
出力: 0
説明: この木の前順走査は「5 9 0 1 2 5」の順に行われます。したがって、9の後続ノードは0となります。

解法のアプローチ

1. 素朴な解法

二分木全体の前順走査をあらかじめ求めておき、与えられた値の次に現れる要素を出力する方法です。考え方はシンプルですが、木全体を走査する必要があるため、効率はあまり良くありません。

2. 効率的な解法

ノードの位置に着目し、後続ノードを直接求める方法です。以下のルールに従って探索します。

• ノードに左の子が存在する場合 → その左の子が後続ノード
• ノードが葉であり、親の左の子である場合 → 兄弟ノード(親の右の子)が後続ノード
• ノードが葉であり、親の右の子である場合 → 「自分が左の子であるような祖先」を上方向へ探索し、その祖先の右の子が後続ノード。該当する祖先が存在しない場合、後続ノードは存在しません(NULL)

この方法では木の高さ分の探索で済むため、時間計算量はO(h)(hは木の高さ)と非常に効率的です。

実装例(C++)

以下のプログラムで、解法がより明確になります。

#include <iostream>
using namespace std;
struct Node {
   struct Node *left, *right, *parent;
   int key;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->left = temp->right = temp->parent = NULL;
   temp->key = key;
   return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
   if (n->left)
      return n->left;
   Node *curr = n, *parent = curr->parent;
   while (parent != NULL && parent->right == curr) {
      curr = curr->parent;
      parent = parent->parent;
   }
   if (parent == NULL)
      return NULL;
   return parent->right;
}
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* preOrder = preOrderSuccessorNode(root, root->left->right);
   if (preOrder) {
      cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
   } else {
      cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
   }
   return 0;
}

出力

Preorder successor of 50 is 26

この例では、ノード50は葉であり、親ノード4の右の子にあたります。そこで「自分が左の子であるような祖先」を上方向へ辿ると根ノード99が該当し、その右の子である26が50の後続ノードとして返されます。