C++でのバイナリツリーのプレオーダートラバーサルでn番目のノードを検索します

この問題では、二分木と整数Nが与えられます。タスクは、二分木のプレオーダートラバーサルで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