ตรวจสอบว่าไบนารีทรีถูกจัดเรียงตามระดับหรือไม่ใน C++

ที่นี่เราจะมาดูวิธีการตรวจสอบไบนารีทรีว่ามีการจัดเรียงระดับที่ชาญฉลาดหรือไม่ ต้นไม้ไบนารีที่เรียงลำดับอย่างชาญฉลาดจะมีลักษณะดังนี้ -

ในแต่ละระดับ โหนดจะถูกจัดเรียงจากซ้ายไปขวา และแต่ละชั้นมีค่าที่สูงกว่าระดับก่อนหน้า

เราสามารถแก้ปัญหานี้ได้โดยดำเนินการข้ามผ่านคำสั่งระดับ และติดตามองค์ประกอบต่ำสุดและสูงสุดของระดับปัจจุบัน ใช้ตัวแปรอื่น prev_max เพื่อเก็บค่าสูงสุดของระดับก่อนหน้า จากนั้นเปรียบเทียบค่าต่ำสุดของระดับปัจจุบันและค่าสูงสุดของระดับก่อนหน้า prev_max หากค่าต่ำสุดมากกว่า prev_max ต้นไม้จะถูกจัดเรียงตามระดับจนถึงระดับปัจจุบัน จากนั้นอัปเดต prev_max และอัปเดตค่าสูงสุดของระดับปัจจุบัน ทำซ้ำจนกว่าจะไม่ผ่านทุกระดับ

ตัวอย่าง

#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";
}

ผลลัพธ์

Tree is level wise Sorted