C++で順序トラバーサルのn番目のノードを検索します

この問題では、二分木と整数Nが与えられます。タスクは、二分木を順番に走査するn番目のノードを見つけることです。

二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。

トラバーサルは、ツリーのすべてのノードにアクセスするプロセスであり、それらの値も出力する場合があります。

問題を理解するために例を見てみましょう

入力

N = 6

出力

3

説明

inorder traversal of tree : 4, 2, 5, 1, 6, 3, 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 findInOrderTraversalRec(struct Node* node, int N){
   static int count = 0;
   if (node == NULL)
      return;
   if (count <= N) {
      findInOrderTraversalRec(node->left, N);
      count++;
      if (count == N)
         cout<<node->data;
      findInOrderTraversalRec(node->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 inorder traversal is ";
   findInOrderTraversalRec(root, N);
   return 0;
}

出力

6th node in inorder traversal is 3