一千萬個為什麽

搜索

如何在二叉搜索樹中找到與給定鍵值最接近的元素?

給定帶有整數值的bst作為鍵如何在bst中找到最接近該鍵的節點? BST使用節點對象(Java)表示。最接近的是例如4,5,9,如果鑰匙是6,它將返回5 ..

最佳答案

像找到元素一樣遍歷樹。當您這樣做時,記錄最接近您的鍵的值。現在,當您沒有找到密鑰本身的節點時,返回記錄的值。

因此,如果您在下面的樹中尋找密鑰 3 ,您將最終在節點 6 上找不到匹配但您的記錄值將是 2 因為這是您遍歷的所有節點中最接近的鍵( 276 )。

                 2
              1      7
                   6   8

轉載註明原文: 如何在二叉搜索樹中找到與給定鍵值最接近的元素?