Trong bài toán này, chúng ta được cung cấp một cây nhị phân và hai cấp trong cây (trên và dưới) và chúng ta phải in tất cả các nút giữa cấp trên và cấp dưới của cây.
Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút (một / hai / không có).
Hãy lấy một ví dụ để hiểu vấn đề -
trên - 1
thấp hơn - 3
Đầu ra -
6 3 9 7 4 8 10
Để giải quyết vấn đề này, chúng ta phải in các nút của cây ở một mức nhất định. Chúng tôi sẽ gọi một hàm đệ quy bằng cách sử dụng một vòng lặp từ upper để thấp hơn cấp trong cây.
Thuật toán này đơn giản nhưng phức tạp hơn theo thứ tự n 2 .
Một giải pháp hiệu quả hơn là thực hiện việc duyệt qua inorder và sử dụng một hàng đợi. Và in các nút trong các cấp trên và dưới đã cho.
Chương trình triển khai giải pháp của chúng tôi -
Ví dụ
#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;
} Đầu ra
Level wise Nodes between level 1 and 3 are 6 3 9 7 4