发现小于X的所有号码在BST [英] finding all numbers less than x in a BST

问题描述

我将如何做到这一点？我不知道当我将停止BST搜索。

how would i do this? I am not sure when I would stop the bst search.

推荐答案

如果你的树的每个节点都有 numLeft 字段，告诉你有多少个节点有在其左子树（计算本身也是如此），那么您可以在 O（日志N）

If each node of your tree has a field numLeft that tells you how many nodes there are in its left subtree (counting itself too), then you can do this in O(log N)

只要保持添加 numLeft 来一个全局结果变量对每个节点的值小于 X ：

Just keep adding numLeft to a global result variable for each node whose value is less than 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)

这将只计算的数字。如果你想打印出来，你需要编写，将打印给定的参数子树的深度优先遍历。你可以找到很多这样的网上，所以我不会发表。

This will only count the numbers. If you want to print them, you need to write a depth first traversal that will print a subtree given as parameter. You can find plenty of those online, so I won't post that.

这篇关于发现小于X的所有号码在BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！