algorithm - 在 BST 中找到所有小于 x 的数字

Question

我该怎么做？我不确定什么时候会停止 bst 搜索。

Answer 1

如果你的树的每个节点都有一个字段 numLeft 告诉你它的左子树中有多少个节点(也计算它自己)，那么你可以在 O(log N)

只需将 numLeft 添加到每个值小于 x 的节点的全局结果变量中:

countLessThan(int x, node T)
    if T = null
        return
    if T.value >= x
        countLessThan(x, T.left) // T.left contains only numbers < T.value and T.right only numbers > T.value
    else
        globalResult += T.numLeft
        countLessThan(x, T.right)

这只会计算数字。如果你想打印它们，你需要编写一个深度优先遍历，它将打印一个作为参数给出的子树。你可以在网上找到很多，所以我不会发布。