在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的數字

回答

相關問題