Inorder在BST中遍歷

Question

我有一個整數的平衡二叉搜索樹，我想找到最大的節點，它存儲的整數大於或等於一個固定的數字，如a使用函數如ask(a)。

例如假設我在我的樹添加了以下幾點，8,10,3,6,1,4,7,14,13

那棵樹會是這樣：

現在ask(1)應該1，ask(3)應該3 ，ask(2)應該是3等等。

我覺得我可以用Inorder遍歷來寫我的ask函數，但是我不知道如何。

Ⅳ書面這段代碼到目前爲止：

inorderFind(node->left, a); 
if (node->key.getX() >= a) 
    return node; 
inorderFind(node->right, a); 

第一個參數是當前樹節點，並a是a上面說明。我知道當if條件成立時，我可以使用一個bool變量，如flag，並將其設置爲true，然後它將防止走過樹的其他節點並返回假節點。還有什麼我可以做的嗎？

Answer 1

樹具有允許通過簡單的遞歸算法查詢的奇妙屬性。所以，我們試着找到你的查詢的遞歸公式。

說LEFTMOST(u)是回答這個問題的函數：

鑑於二叉搜索樹紮根在節點u，與（可能爲null）左， 沒錯兒l和r，分別是什麼左最節點 與價值>= a？

的關係很簡單：

LEFTMOST(u) = LEFTMOST(l) if it exists 
       LEFTMOST(r) otherwise 

就是這樣。如何將這個問題轉化爲您的問題，以及如何處理「空」和「不存在」等概念是您表示的一種功能。