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

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

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

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

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

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

Input: 1
Output: 9

この問題を解決するには、 navie アプローチは、二分木のプレオーダートラバーサルを見つけて、指定された番号の後に続く要素を出力することです。

より効果的な解決策は、指定された番号の位置を確認し、位置に基づいてその前身を検索することです。ノードがルートノードの場合、先行ノードではなくNULLを返します。ノードが右の子である場合、左の子が先行子になります。

ソリューションの実装を示すプログラム

例

#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