Ở đây chúng ta sẽ xem cách kiểm tra một cây nhị phân có được sắp xếp theo cấp độ khôn ngoan hay không. Cây nhị phân được sắp xếp theo cấp độ khôn ngoan sẽ giống như bên dưới -
Trong mỗi cấp, các nút được sắp xếp từ trái sang phải và mỗi lớp chứa giá trị cao hơn cấp trước của nó.
Chúng tôi có thể giải quyết vấn đề này bằng cách thực hiện duyệt qua thứ tự cấp và theo dõi các yếu tố tối thiểu và tối đa của cấp hiện tại. Sử dụng một biến pres_max khác để giữ giá trị lớn nhất của mức trước đó. Sau đó, so sánh giá trị nhỏ nhất của mức hiện tại và giá trị lớn nhất của mức trước đó. Nếu giá trị min lớn hơn pres_max, thì cây sẽ được sắp xếp theo mức thông thường cho đến mức hiện tại. Sau đó, cập nhật pres_max và cập nhật giá trị tối đa của mức hiện tại. Lặp lại điều này cho đến khi tất cả các cấp không bị vượt qua.
Ví dụ
#include <iostream>
#include <queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLevelWiseSorted(Node* root) {
int prevMax = INT_MIN;
int min_val, max_val;
int levelSize;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
levelSize = q.size();
min_val = INT_MAX;
max_val = INT_MIN;
while (levelSize > 0) {
root = q.front();
q.pop();
levelSize--;
min_val = min(min_val, root->key);
max_val = max(max_val, root->key);
if (root->left)
q.push(root->left);
if (root->right)
q.push(root->right);
}
if (min_val <= prevMax)
return false;
prevMax = max_val;
}
return true;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
if (isLevelWiseSorted(root))
cout << "Tree is levelwise Sorted";
else
cout << "Tree is Not levelwise sorted";
} Đầu ra
Tree is level wise Sorted