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