Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình in các nút giữa hai số cấp độ cho trước của một cây nhị phân.
Trong bài toán này, chúng ta được cho một cấp độ thấp (low) và một cấp độ cao (high) cho một cây nhị phân cụ thể và chúng ta phải in tất cả các phần tử giữa các cấp độ cho trước.
Để giải quyết bài toán này, chúng ta có thể sử dụng duyệt theo cấp độ dựa trên hàng đợi (queue-based level traversal). Trong khi di chuyển qua duyệt inorder, chúng ta có thể có một nút đánh dấu (marking node) ở cuối mỗi cấp độ. Sau đó, chúng ta có thể đi đến từng cấp độ và in các nút của nó nếu nút đánh dấu tồn tại giữa các cấp độ cho trước.
Ví dụ
#include <iostream> #include <queue> using namespace std; struct Node{ int data; struct Node* left, *right; }; //to print the nodes between the levels void print_nodes(Node* root, int low, int high){ queue <Node *> Q; //creating the marking node Node *marker = new Node; int level = 1; Q.push(root); Q.push(marker); while (Q.empty() == false){ Node *n = Q.front(); Q.pop(); //checking for the end of level if (n == marker){ cout << endl; level++; if (Q.empty() == true || level > high) break; Q.push(marker); continue; } if (level >= low) cout << n->data << " "; if (n->left != NULL) Q.push(n->left); if (n->right != NULL) Q.push(n->right); } } Node* create_node(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return (temp); } int main(){ struct Node *root= create_node(20); root->left= create_node(8); root->right= create_node(22); root->left->left= create_node(4); root->left->right= create_node(12); root->left->right->left= create_node(10); root->left->right->right= create_node(14); cout << "Elements between the given levels are :"; print_nodes(root, 2, 3); return 0; }
Kết quả
Elements between the given levels are : 8 22 4 12