二進制搜索樹Java中的迭代上限方法

Question

我正在處理一個問題，因爲我困在類上。它涉及到在這裏找到的二進制搜索樹中添加一個方法：http://algs4.cs.princeton.edu/32bst/BST.java.html

我需要開發一個迭代上限方法，找到給定密鑰的上限。它不能遞歸。

這是我的代碼到目前爲止。我理解我應該實現的算法的基礎知識，但是我發現實際上很難繞過我的頭。

在此先感謝您提供的任何幫助。

public Key ceiling_i(Key key) 
{ 
    Node t = root; 
    for(int i = 0; i < size(); i++){ 
     int cmp = key.compareTo(t.key); 
     if(cmp == 0) return t.key; 
     else if(cmp < 0) t = t.left; 
     else if(cmp > 0) t = t.right; 

    } 
    return null; 
} 

編輯：我遇到的主要問題是如何處理第一個之後的迭代。根據我的書，「如果給定的密鑰大於BST根的密鑰，那麼密鑰的上限（BST中的最大密鑰大於或等於密鑰）必須位於右側子樹中。如果密鑰是 小於根的密鑰，那麼密鑰的上限可以是 位於左子樹中;如果不是（或者如果密鑰等於根中的密鑰 ），那麼根上的密鑰是鑰匙的天花板「。我不知道如何處理在循環中的。

Answer 1

你的代碼是一個好的開始。但你的循環對我來說沒有意義。

public Key ceiling_i(Key key) 
{ 
    Node t = root; 
    Node t largestVisited = null; 
    while(t != null) { 
     int cmp = key.compareTo(t.key); 
     if(cmp == 0) return t.key; 
     else if(cmp < 0) { largestVisited = Min(t, largestVisited); t = t.left; } 
     else if(cmp > 0) { t = t.right; largestVisited = Min(t, largestVisited); } 

    } 
    return largestVisited; 
} 

Node Min(Node a, Node b) { return the node with the smaller key; } 

提示：您可以通過先寫遞歸解決方案，並注意到這是尾遞歸已經得出此代碼。通過重用已經存在的局部變量，尾遞歸函數可以簡單地做成非遞歸函數。如果您不再使用舊的堆棧，則無需再打開另一個堆棧。

Answer 2

該書中的代碼不是尾遞歸的，因爲第一個ceiling（）調用在返回之前在其上執行了操作。

private Node ceiling(Node x, Key key) { 
    if (x == null) return null; 
    int cmp = key.compareTo(x.key); 
    if (cmp == 0) return x; 
    if (cmp < 0) { 
     Node t = ceiling(x.left, key); 
     if (t != null) return t; 
     else return x; 
    } 
    return ceiling(x.right, key); 
} 

更改ceilng（）所以遞歸調用是一個「累加器」類型的尾調用。通過傳遞額外的參數來完成這項工作，這些參數包含迄今爲止完成的工作。

cmp時，空或節點作爲x.left傳遞< 0.到目前爲止，「累積」的是在此條件測試中發現的大於項目的節點x。

在第一次遞歸調用後的原始版本中，t是null或某個樹節點。如果t爲空，則使用節點x。在修改版本中，附加參數將傳遞給x節點。

在尾部調用cmp> 0的另一個條件測試中，沒有新的「累積」工作，因爲x小於該項目，並且在x.right爲空時不用於確定返回值。

注意如果我們在修改後的天花板（x，鍵，更大）函數中將「累計x」傳遞給「更大」，會發生什麼情況。在這個修改的函數中，條件「if（x == null）return null」被替換爲「if（x == null）返回更大」，並且在第一次遞歸調用之後所有t值評估都被刪除。第二次尾部調用只是將空值傳遞給更大。

所以轉換應該是這個樣子：

private Node ceiling (Node x, Key key, Node larger) { 
    if (x == null) return larger; 
    int cmp = key.compareTo(x.key); 
    if (cmp == 0) return x; 
    if (cmp < 0) { 
     return ceiling(x.left, key, x); 
    } 
    return ceiling(x.right, key, null); 
} 

現在的功能是尾遞歸，可以進一步轉化爲迭代循環形式。

private Node ceiling (Node x, Key key) { 
    Node larger = null; 
    while (x != null) { 
     int cmp = key.compareTo(x.key); 
     if (cmp == 0) return x; 
     if (cmp < 0) { 
      larger = x; 
      x = x.left; 
     } else { 
      x = x.right; 
     } 
    } 
    return larger; 
}