C++의 이진 트리에 있는 노드의 선행 주문 선주문

이 문제에서는 이진 트리와 노드 값이 제공됩니다. 우리의 임무는 노드의 선행 주문을 인쇄하는 것입니다.

이진 트리 각 루트 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 유형의 트리입니다.

선주문 순회 트리의 노드를 탐색하는 방법입니다. 여기에서 먼저 루트 노드를 순회한 다음 왼쪽 자식, 오른쪽 자식을 순회합니다.

선주문 선행 노드 노드의 선주문 순회에서 노드 앞에 오는 노드입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

Input: 1
Output: 9

이 문제를 해결하기 위해 네이비 접근 방식은 이진 트리의 선주문 순회를 찾은 다음 주어진 숫자 뒤에 오는 요소를 인쇄하는 것입니다.

보다 효과적인 솔루션은 주어진 번호의 위치를 ​​확인한 다음 위치를 기반으로 이전 번호를 검색하는 것입니다. 노드가 루트 노드이면 선행 작업이 없는 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