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

我该怎么做？我不知道什么时候会停止bst搜索。在BST中找到所有小于x的数字

2010-06-27 ryanxu

我只是想知道如何将我修改BST搜索，获得小于X的元素个数 – ryanxu 2010-06-27 07:46:24

如果树的每个节点都有一个场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)

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

来源

2010-06-27 07:46:18 IVlad

不知道这是不是你正在寻找或不是，但二叉搜索树算法是经典的，互联网充满了他们。 http://www.algolist.net/Data_structures/Binary_search_tree/Lookup - 至少应该让你朝着正确的方向前进（你会想修改'found'条件并返回'collection'而不是bool）。

来源

2010-06-27 07:42:56

如果您需要列表中的数字，您仍然需要遍历树。对于BST，您可以从最低到最高进行遍历。
但是如果你需要子树代表最低的数字：

def splitLowerTree(x, node): 
    if node is None: return None 
    elif node.value == x: return node.left 
    elif node.value < x: 
     if node.right is None: return node 
     else: return Node(node.value, left = node.left, right = splitLowerTree(x, node.right)) 
    else: return splitLowerTree(x, node.left)

来源

2010-06-27 07:48:12 ony

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

回答

相关问题