如何在BST中获得小于给定键的所有值

Question

你好，我正在实现一个二进制搜索树。我必须使用二进制搜索找到小于给定密钥的所有元素：

struct node {
int data;
node* right;
node* left;
};
class binTree {
public:
binTree();
~binTree();
void insert(node**, int);
void inOrder(node**)const;
void preOrder(node**)const;
void postOrder(node**)const;
void delTree();
node* search(node**, int)const;
void search_less(node**, int)const;
};
binTree::binTree() {
}
binTree::~binTree() {
}
void binTree::insert(node** root, int data) {
node* tmp = *root;
if (!tmp) {
tmp = new node;
tmp->data = data;
tmp->right = NULL;
tmp->left = NULL;
*root = tmp;
return;
}
if (data < tmp->data)
insert(&tmp->left, data);
else
insert(&tmp->right, data);
}
void binTree::preOrder(node** root)const {
node* tmp = *root;
if (tmp) {
cout << tmp->data << endl;
preOrder(&tmp->left);
preOrder(&tmp->right);
}
}
void binTree::inOrder(node** root)const {
node* tmp = *root;
if (tmp) {
inOrder(&tmp->left);
cout << tmp->data << endl;
inOrder(&tmp->right);
}
}
void binTree::postOrder(node** root)const {
node* tmp = *root;
if (tmp) {
postOrder(&tmp->left);
postOrder(&tmp->right);
cout << tmp->data << endl;
}
}
node* binTree::search(node** root, int data)const {
node* tmp = *root;
if (tmp) {
if (data == tmp->data) {
cout << "found!" << endl;
return tmp;
}
else
if (data < tmp->data)
search(&tmp->left, data);
else
search(&tmp->right, data);
}
cout << data << ": not found in tree!" << endl;
return NULL;
}
void binTree::search_less(node** root, int key)const
{
node* tmp = *root;
tmp = search(root, key);
}
int main()
{
node* root = NULL;
binTree bt;
bt.insert(&root, 42000);
bt.insert(&root, 41000);
bt.insert(&root, 45000);
bt.insert(&root, 47000);
bt.insert(&root, 42500);
bt.insert(&root, 43000);
bt.insert(&root, 44000);
bt.insert(&root, 40000);
bt.insert(&root, 10000);
bt.insert(&root, 20000);
bt.insert(&root, 30000);
bt.search_less(&root, 42000); // I want to get values smaller than 42000
}

• 我试了太多，但都想不通。我想打印输入的键下面的所有值。谢谢

Answer 1

1. 创建累加器std::vector<T>
2. 将根节点设置为当前节点
3. 如果当前节点是nullptr，则转到6(完成(
4. 如果当前节点>=搜索值，则将左侧节点设置为当前节点，然后转到3
5. 如果当前节点<搜索值，累加该值并累加左节点的整个子树。将右侧节点设置为当前节点，然后转到3
6. 返回蓄能器

累积整个左节点应该是它自己的函数(accumulate_entire_tree或类似的函数(。递归函数应该是步骤3-5。步骤1-6是整个包装器函数。最后你得到三个功能：

1. std::vector<int> search_less_than(const Node& root, int key) const
2. void accumulate_less_than(const Node* root, int key, std::vector<int>& accumulator) const
3. void accumulate_entire_tree(const Node* root, std::vector<int>& accumulator) const

将最后两个函数设为私有函数，因为它们更多的是实现细节，而不是接口。

Answer 2

您可以制作类似于search函数的东西：

void binTree::search_less(node** root, int data) const {
node* tmp = *root;
if (tmp) {
if (data > tmp->data) {
search_less(&tmp->left, data);
cout << tmp->data << endl;
search_less(&tmp->right, data);
} else {
search_less(&tmp->left, data);
}
}
}

演示

Answer 3

如果密钥存在，那么它很简单：在search_less内部使用yur函数search找到密钥，然后将其节点传递给inOrder或postOrder。。。

如果你想得到比不存在的密钥更小的值：这有点棘手：

• 如果键小于根节点数据，则向左移动，直到数据小于键或等于键，然后将该节点传递到inOrder或postOrder。

  • 如果键大于根，则向右移动，直到具有数据的节点小于或等于它，然后执行第一步并打印。

    void binTree::search_less(node** root, int data)const
    {
    node* tmp = *root;
    if (tmp && tmp->data < data)
    tmp = tmp->right;
    while (tmp && tmp->data >= data)
    tmp = tmp->left;
    inOrder(&tmp);
    }
    

Answer 4

我花了相当多的时间和精力独自找到这个解决方案：

void binTree::search_less(node** root, int key)const 
{
node* tmp = *root;
if(tmp)
{
search_less(&tmp->left, key);
if(key <= tmp->data)
return;
search_less(&tmp->right, key);
std::cout << tmp->data << ", ";   
}
} 

int main() 
{
node* root = NULL; 
binTree bt; 
bt.insert(&root, 42000); 
bt.insert(&root, 41000); 
bt.insert(&root, 45000); 
bt.insert(&root, 47000); 
bt.insert(&root, 42500);
bt.insert(&root, 43000); 
bt.insert(&root, 44000); 
bt.insert(&root, 40000); 
bt.insert(&root, 10000); 
bt.insert(&root, 20000); 
bt.insert(&root, 30000); 
bt.search_less(&root, 37500);
std::cout << "nDone!n";
}

输出：

30000, 20000, 10000,
Done!
[Process completed - press Enter]

• 我在递归中走得最左边，直到我使用"inOrder"方法获得树中的最小值，因为它可以从小到大排序值。然后打印出来，向右走，检查数据是否大于或等于键，在这种情况下停止并返回。

• 请告诉我这是否是一个正确有效的解决方案？