C++에서 이진 트리의 선주문 순회에서 n번째 노드 찾기

이 문제에서 우리는 이진 트리와 정수 N이 주어집니다. 작업은 이진 트리의 Preorder traversal에서 n번째 노드를 찾는 것입니다.

바이너리 트리에는 각 노드가 최대 2개의 자식을 가질 수 있다는 특수한 조건이 있습니다.

순회는 트리의 모든 노드를 방문하는 프로세스이며 해당 값도 출력할 수 있습니다.

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

입력

N = 6

출력

6

설명

Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 7

솔루션 접근 방식

아이디어는 재귀 호출을 사용하여 수행되는 이진 트리의 선주문 순회를 사용하는 것입니다. 각 호출에서 루트 노드를 방문한 다음 먼저 왼쪽 하위 트리에 대해 preOrder()를 호출한 다음 preOrder()를 호출합니다. 이 순회 동안 우리는 노드의 수를 세고 카운트가 N인 노드를 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
struct Node* createNode(int item){
   Node* temp = new Node;
   temp->data = item;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void findPreOrderTraversalRec(struct Node* root, int N){
   static int nodeCount = 0;
   if (root == NULL)
      return;
   if (nodeCount <= N) {
      nodeCount++;
      if (nodeCount == N)
         cout << root->data;
         findPreOrderTraversalRec(root->left, N);
         findPreOrderTraversalRec(root->right, N);
      }
   }
   int main() {
      struct Node* root = createNode(1);
      root->left = createNode(2);
      root->right = createNode(3);
      root->left->left = createNode(4);
      root->left->right = createNode(5);
      root->right->left = createNode(6);
      root->right->right = createNode(7);
      int N = 6;
      cout<<N<<"th node in preorder traversal is ";
      findPreOrderTraversalRec(root, N);
      return 0;
}

출력

6th node in preorder traversal is 6