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