C++のバイナリツリーでノードの後続を事前注文する

この問題では、二分木とノード値が与えられます。私たちのタスクは、ノードのプレオーダーサクセサを印刷することです。

二分木 は、各ルートノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。

プレオーダートラバーサル ツリーのノードをトラバースする方法です。ここでは、最初にルートノードをトラバースし、次に左の子、次に右の子をトラバースします。

後続ノードの事前注文 ノードのプレオーダートラバーサルでノードの隣に来るノードです。

問題を理解するために例を見てみましょう

Input: 9
Output
0
Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.

この問題を解決するための簡単なアプローチは、バイナリツリーのプレオーダートラバーサルを見つけて、指定された番号の後に続く要素を出力することです。

より効果的な解決策は、与えられた番号の位置をチェックし、位置に基づいてその後継者を検索することです。したがって、ポジションに左の子がある場合、事前注文の後継者は左の子になります。リーフノードであるが子のままである場合、その兄弟ノードはプレオーダーサクセサです。リーフノードであり、子が残っていない場合は、子ノードがプレオーダーの後続ノードとなる祖先ノードに移動する必要があります。

プログラムは解決策をより明確にします

例

#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