C++의 이진 트리에서 주어진 두 수준 사이의 모든 노드 인쇄

이 문제에서는 이진 트리와 트리의 두 수준(상위 및 하위)이 주어지고 트리의 상위 및 하위 수준 사이의 모든 노드를 인쇄해야 합니다.

이진 트리 각 노드가 최대 2개의 노드(1/2/없음)를 갖는 특수 트리입니다.

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

상위 − 1

낮음 - 3

출력 -

6
3 9
7 4 8 10

이 문제를 해결하려면 주어진 수준에서 트리의 노드를 인쇄해야 합니다. 위쪽 에서 루프를 사용하여 재귀 함수를 호출합니다. 낮추기 트리의 레벨입니다.

이 알고리즘은 간단하지만 n ² 차수가 더 복잡합니다. .

보다 효과적인 솔루션은 inorder traversal을 수행하고 대기열을 사용하는 것입니다. 그리고 주어진 상위 및 하위 레벨 내의 노드를 인쇄합니다.

솔루션 구현을 위한 프로그램 −

예시

#include <iostream>
#include <queue>
using namespace std;
struct Node{
   int key;
   struct Node* left, *right;
};
void printNodesAtLevel(Node* root, int low, int high){
   queue <Node *> Q;
   Node *marker = new Node;
   int level = 1;
   Q.push(root);
   Q.push(marker);
   while (Q.empty() == false){
      Node *n = Q.front();
      Q.pop();
      if (n == marker){
         cout << endl;
         level++;
         if (Q.empty() == true || level > high) break;
         Q.push(marker);
         continue;
      }
      if (level >= low)
         cout<<n->key<<" ";
      if (n->left != NULL) Q.push(n->left);
      if (n->right != NULL) Q.push(n->right);
   }
}
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return (temp);
}
int main() {
   struct Node *root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(9);
   root->left->left = insertNode(7);
   root->left->right = insertNode(4);
   root->left->right->left = insertNode(8);
   root->left->right->right = insertNode(10);
   root->left->right->right->left = insertNode(5);
   root->left->right->right->right = insertNode(1);
   root->left->right->left->left = insertNode(14);
   root->left->right->left->right = insertNode(26);
   int upper = 3;
   int lower = 1;
   cout << "Level wise Nodes between level "<<lower<<" and "<<upper<<" are \n";
   printNodesAtLevel(root, lower, upper);
   return 0;
}

출력

Level wise Nodes between level 1 and 3 are
6
3 9
7 4