如何获得小于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

您可以使用search函数，然后仅在节点的左侧打印42000值，如：

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

Demo

Answer 2

1. 创建累加器std::vector<T>
2. 将根节点设置为当前节点
3. 如果当前节点为nullptr，则转到6（完成）
4. 如果当前节点是> =搜索值，则将左节点设置为当前节点并转到3
5. 如果当前节点是
6. 返回累加器

累加整个左节点应该是它自己的功能（accumulate_entire_tree或类似的东西）。递归函数应为步骤3-5。步骤1-6是整个包装函数。最后，您将获得三个功能：

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

将后两个功能设为私有，因为它们是比接口更多的实现细节。