时间戳

首页 > 解决方案 > BST 中大于给定 KEY 的节点数

c++ - BST 中大于给定 KEY 的节点数

问题描述

我编写了下面的代码来计算BST 中大于给定 KEY 的节点数：

int Tree::findNumbersThatBiggerThanKey(int key){
    return PrivateFindNumbersThatBiggerThanKey(key, this->rootNode);
}

int Tree::PrivateFindNumbersThatBiggerThanKey(int key, Node* start) {
    if (!start)
        return 0;

    if (start->key > key)
        return 1 + this->PrivateFindNumbersThatBiggerThanKey(key, start->leftNode) +
        this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

    else if (start->key < key)
        return this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

    else /*start->key > key*/
        return this->PrivateFindNumbersThatBiggerThanKey(key, start->leftNode);
}

这是我的主要内容：

int main() {

    int TreeKeys[16] = { 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80 };
    Tree myBst;

    cout << "Printing the three Inorder before adding numbers: \n";
    myBst.printInorder();


    for (int i = 0; i < 16; i++) {
        myBst.AddLeaf(TreeKeys[i]);
    }

    cout << "Printing the three Inorder after adding numbers: \n";
    myBst.printInorder();

    int key = 2;
    cout << "\n\nNumber of nodes that are bigger than "<<key<<" : " <<
         myBst.findNumbersThatBiggerThanKey(key);
    return 0;
}

Inroder 打印效果很好：

Printing the three Inorder after adding numbers:
2 3 4 14 15 21 32 50 52 64 70 76 80 83 87 100

但是当我搜索大于“2”的节点数时，我得到 14 个不正确的节点（而不是 15 个）：

Number of nodes that are bigger than 2 : 14

当我搜索大于“1”的节点数时，我得到 16，这是正确的结果（对于任何其他数字，我也得到了正确的结果）：

Number of nodes that are bigger than 1 : 16

我是递归的学生和新手，我会很高兴解释为什么会发生这种情况以及如何解决它。

标签： c++binary-search-tree

解决方案

你else的不正确，它的条件是start->key == key应该被视为相同start->key < key

所以重写它

else 
   return this->PrivateFindNumbersThatBiggerThanKey(key, start->rightNode);

或者简单地将它与start->key < key

推荐阅读