資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的 BST 地板和天花板
在這裡，我們將瞭解如何從 BST 中找到地板和天花板值。例如，如果我們想建立一個記憶體管理系統，其中空閒節點以 BST 的形式排列。找到對輸入請求的最佳匹配。假設我們正在沿著樹向下移動，資料大於鍵值且最小，則有三種可能的情況。
- 根節點是鍵。則根節點值是天花板值
- 如果根節點資料 < 鍵，則天花板值不會在左子樹中，然後繼續到右子樹，並縮小問題域
- 如果根節點資料 > 鍵，則天花板值可能在右子樹中，我們可能在左子樹中找到一個數據大於鍵的節點，如果沒有這樣的元素，則根節點是天花板值。
假設樹是這樣的 -
0、1、2 的天花板是 2，3、4 的天花板是 4，依此類推
這裡我們只看天花板函式，如果我們稍微修改一下，就可以得到地板值。
示例
#include <iostream>
using namespace std;
class node {
public:
int key;
node* left;
node* right;
};
node* getNode(int key) {
node* newNode = new node();
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int ceiling(node* root, int num) {
if (root == NULL)
return -1;
if (root->key == num)
return root->key;
if (root->key < num)
return ceiling(root->right, num);
int ceil = ceiling(root->left, num);
return (ceil >= num) ? ceil : root->key;
}
int main() {
node* root = getNode(8);
root->left = getNode(4);
root->right = getNode(12);
root->left->left = getNode(2);
root->left->right = getNode(6);
root->right->left = getNode(10);
root->right->right = getNode(14);
for (int i = 0; i < 16; i++)
cout << i << "\tCeiling: " << ceiling(root, i) << endl;
}輸出
0 Ceiling: 2 1 Ceiling: 2 2 Ceiling: 2 3 Ceiling: 4 4 Ceiling: 4 5 Ceiling: 6 6 Ceiling: 6 7 Ceiling: 8 8 Ceiling: 8 9 Ceiling: 10 10 Ceiling: 10 11 Ceiling: 12 12 Ceiling: 12 13 Ceiling: 14 14 Ceiling: 14 15 Ceiling: -1
更新於: 2019年10月21日
193 次檢視
廣告