พิมพ์คีย์ BST ในช่วงที่กำหนด - O (1) Space ใน C ++

ในปัญหานี้ เราได้รับสองค่า k1 และ k2 (k1 พิมพ์คีย์ BST ในช่วงที่กำหนด

คำอธิบายปัญหา: เราจะพิมพ์คีย์ทั้งหมดของต้นไม้ตั้งแต่ n1 ถึง n2 ตามลำดับที่เพิ่มขึ้น

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล:

k1 =4, k2 =12

ผลลัพธ์: 6, 7, 9

แนวทางการแก้ปัญหา

ง่าย เราสามารถแก้ปัญหาโดยใช้ การข้ามผ่าน แต่ความซับซ้อนของพื้นที่มี 0(n) แต่ความต้องการของชั่วโมงคือการแก้ในความซับซ้อน O(1) สำหรับสิ่งนี้ เราจะใช้เทคนิคการข้ามผ่านแบบพิเศษ

เราจะใช้ Morris Traversal ซึ่งขึ้นอยู่กับต้นไม้ไบนารีแบบเธรด ไม่ต้องใช้สแต็ก/คิวใดๆ และใช้พอยน์เตอร์ NULL เพื่อจัดเก็บข้อมูล ซึ่งช่วยลดพื้นที่จัดเก็บเป็น O(1)

โปรแกรมแสดงการทำงานของมอร์ริสทราเวอร์แซลเพื่อแก้ปัญหา

ตัวอย่าง

#include <iostream>
using namespace std;

struct node {
   int data;
   struct node *left, *right;
};

node* insertNode(int data) {
   node* temp = new node;
   temp->data = data;
   temp->right = temp->left = NULL;
   return temp;
}

void RangeTraversal(node* root, int k1, int k2) {
   
   if (!root)
      return;
     
   node* nodeTraversal = root;

   while (nodeTraversal) {

      if (nodeTraversal->left == NULL) {

         if (nodeTraversal->data <= k2 &amp;&amp; nodeTraversal->data >= k1)
         
            cout<<nodeTraversal->data<<" ";
         nodeTraversal = nodeTraversal->right;
      }

      else {
         node* prevNode = nodeTraversal->left;
         while (prevNode->right != NULL &amp;&amp; prevNode->right != nodeTraversal)
            prevNode = prevNode->right;

         if (prevNode->right == NULL) {
            prevNode->right = nodeTraversal;
            nodeTraversal = nodeTraversal->left;
         }
         else {
            prevNode->right = NULL;
            if (nodeTraversal->data <= k2 &amp;&amp; nodeTraversal->data >= k1)
               cout<<nodeTraversal->data<<" ";
            nodeTraversal = nodeTraversal->right;
         }
      }
   }
}

int main() {
   node* root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(2);
   root->left->left = insertNode(1);
   root->left->right = insertNode(7);
   root->right->right = insertNode(9);

   cout<<"All BST keys in the given range are \t";
   RangeTraversal(root, 4, 10);
   
   return 0;
}

ผลลัพธ์

All BST keys in the given range are 7 6 9