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 的左孩子。这是因为我快速而肮脏的 BST 实现只允许右孩子在已经有左孩子的情况下）：

      8
    /   \
  3       14
 / \     /
1   6   10

Answer 2

你可以这样做：

int res = countLessThan(root, value, 0); // res is your answer

然后实现这个：

int BTree::countLessThan(node *currNode, int value, int count)
{            
        if(currNode->left != NULL)
                count = countLessThan(currNode->left, value, count);

        if(currNode->value >= value)
                return count;
        count++;

        if(currNode->right != NULL)
                count = countLessThan(currNode->right, value, count);

       return count;

}

Answer 3

1. 如果您正在使用std::map或std::set作为您的 BST，则可以将std::map::lower_bound成员函数与以下内容结合使用std::distance：

   auto count = std::distance(bst.begin(), bst.lower_bound(target));
   

2. 否则，您可以使用一个std::lower_bound函数，但它只对平面容器 ( std::vector) 是最佳的，因为它假定容器实现了随机访问迭代器。

   auto count = std::distance(
       bst.begin(), std::lower_bound(bst.begin(), bst.end(), target));