我該怎麼做?我不知道什麼時候會停止bst搜索。在BST中找到所有小於x的數字
0
A
回答
2
如果樹的每個節點都有一個場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)
這將只計數的數字。如果你想打印它們,你需要編寫一個深度優先遍歷,它將打印一個作爲參數給出的子樹。你可以在網上找到很多,所以我不會發布。
0
不知道這是不是你正在尋找或不是,但二叉搜索樹算法是經典的,互聯網充滿了他們。 http://www.algolist.net/Data_structures/Binary_search_tree/Lookup - 至少應該讓你朝着正確的方向前進(你會想修改'found'條件並返回'collection'而不是bool)。
0
如果您需要列表中的數字,您仍然需要遍歷樹。對於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)
相關問題
- 1. 查找給定BST中小於給定數字(n)的最大數字
- 2. 在bst中第k個最小數字
- 3. 找到所有正數小於或等於給定數字的總和
- 4. 在排序數組中找到小於x的最大值
- 5. 找到最大的x^y小於數字
- 6. 如何找到BST的最小元素?
- 7. 如何找到我的BST中的最小計數
- 8. 找到所有的數字與小數範圍
- 9. 找到所有的勾股數小於500
- 10. 找到比BST中的給定值更高的值的數字
- 11. MySql的尋找到的數據包含所有行小於4個字符
- 12. 遞歸複製BST的所有樹葉到另一個BST
- 13. 列表理解,找到列表中的每個數字的所有倍數小於一個數字
- 14. Git - 添加所有小於X兆字節的文件
- 15. BST類,找到值
- 16. 在bst中使用遞歸找到kth最小inorder
- 17. 使用PHP來找到小於X字符的單詞在文本文件中
- 18. 查找列表中所有數字的最小整數
- 19. 尋找在BST
- 20. Java:找到在BST中找不到的節點的深度
- 21. 在BST中找到「nth」值(C)
- 22. 找到bst中最小的深度葉節點
- 23. 找到兩個小於X數的最大功率?
- 24. 返回數字數組是小於x
- 25. 刪除值小於x的PriorityQueue中的所有項目
- 26. 如何找到含有數字的子集,所有的數字
- 27. 找到一個數字的更多pythonic方法是最小化所有數字
- 28. 使用AWK找到在第二列中的最小數大於X
- 29. BST中的所有父節點?
- 30. 獲取所有字符,直到找到新的日期/小時
我只是想知道如何將我修改BST搜索,獲得小於X的元素個數 – ryanxu 2010-06-27 07:46:24