주어진 범위에서 BST 키 인쇄 - C++의 O(1) Space

이 문제에서는 두 개의 값 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