c++ - 在二叉搜索树中提取质量

Question

是否有有效的方法来查找二叉搜索树中小于某个元素的所有元素的数量？我一直试图在 C++ 中找到一个过程或实现，但我没能找到。所以说你有:

      8
    /   \
   3     10
  / \      \
 1   6      14

而你想找到小于10的节点数，你可以得到4。

Answer 1

如果您知道给定节点下方有多少个节点(在恒定时间内)，您可以简单地执行以下操作:

int BinarySearchTree::countLessThan(const Node *n, const T &value) const {
    if (n->value >= value) {
        // The value has to be in the left sub-tree, so continue searching there:
        if (n->left)
            return countLessThan(n->left, value);
        else
            return 0;
    } else {
        // The value has to be in the right sub-tree, so continue searching there
        // but include the whole left sub-tree and myself:
        int count = 1;
        if (n->left)
            count += n->left->count();
        if (n->right)
            count += countLessThan(n->right, value);
        return count;
    }
}

在根节点上启动算法:

int BinarySearchTree::countLessThan(const T &value) const {
    countLessThan(root, value);
}

可以在这里看到一个活生生的例子:http://ideone.com/JcpjeK

它在下面的树上运行(我交换了 14 和 10，所以 10 可以是 14 的左 child 。这是因为我快速而肮脏的 BST 实现只允许右 child ，如果已经有左 child ):

      8
    /   \
  3       14
 / \     /
1   6   10