数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中以O(1)空间打印BST中给定范围的键
在这个问题中，我们给定两个值k1和k2 (k1 < k2)，以及二叉搜索树的根节点。我们的任务是编写一个程序来打印给定范围内的BST键。
问题描述：我们将按升序打印树中从n1到n2的所有键。
让我们举个例子来理解这个问题：
输入：
k1 = 4, k2 = 12
输出：6, 7, 9
解决方案
我们可以简单地使用中序遍历来解决这个问题，但是空间复杂度是O(n)，而我们需要的是O(1)的复杂度。因此，我们将使用一种特殊的遍历技术。
我们将使用Morris遍历，它基于线程二叉树。它不需要任何堆栈/队列，并使用NULL指针存储信息，这有助于将存储空间减少到O(1)。
程序演示Morris遍历如何解决这个问题：
示例
#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 && nodeTraversal->data >= k1)
cout<<nodeTraversal->data<<" ";
nodeTraversal = nodeTraversal->right;
}
else {
node* prevNode = nodeTraversal->left;
while (prevNode->right != NULL && prevNode->right != nodeTraversal)
prevNode = prevNode->right;
if (prevNode->right == NULL) {
prevNode->right = nodeTraversal;
nodeTraversal = nodeTraversal->left;
}
else {
prevNode->right = NULL;
if (nodeTraversal->data <= k2 && 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
更新于： 2021年1月25日
95 次浏览
广告