C++で特定のキーの次の右ノードを検索します

この問題では、バイナリツリーBTとキー値が与えられます。私たちのタスクは、特定のキーの次の正しいノードを見つけることです。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。

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

入力

key = 4

出力

5

説明

ノード4の隣の要素は5です。

ソリューションアプローチ

この問題の簡単な解決策は、レベル順トラバーサルを使用してバイナリツリーをトラバースすることです。そして、与えられたキー値について、トラバーサルの同じレベルでノードの隣にノードが存在するかどうかを確認します。はいの場合は次のノードを返し、そうでない場合はNULLを返します。

ソリューションの動作を説明するプログラム

例

#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