資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告