BST的第n個最小元素

Question

給出了BST（二叉搜索樹）T. 如何找到T的第n個最小元素？

Answer 1

二叉搜索樹被有效排序，所以你只需要按順序遍歷樹併到達第n個點。如果樹是完全平衡的，你可以計算要去的地方。

Answer 2

如果二叉搜索樹不完全平衡，那麼您需要執行遞歸搜索以查找第n個最小元素。通過讓每個節點存儲每個分支指針所指向的子節點的數量，可以大大加速這種情況，從而有效地將搜索轉換爲二進制指針。但是，這會增加樹更新的開銷，因爲每次插入或刪除都需要通過葉到根遍歷來更新節點計數。

或者，您可以保持樹平衡，並使用上述答案。