数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告