二叉樹搜索的迭代版本

在二叉搜索樹中搜索節點（值爲k）的基本樹搜索算法。 'x'表示二叉查找樹的節點。二叉樹搜索的迭代版本

TREE-SEARCH (x, k) 
if x= NIL or k = key[x] 
    then return x 
if k < key[x] 
    then return TREE-SEARCH(left[x], k) 
    else return TREE-SEARCH(right[x], k)

迭代版本：

ITERATIVE-TREE-SEARCH(x, k) 
while x ≠ NIL and k ≠ key[x] 
    do if k < key[x] 
      then x ← left[x] 
      else x ← right[x] 
return x

不宜（迭代算法）的第一行實際上是同時（X≠NIL或K≠鍵[X]）代替（而X≠ NIL和k≠鍵[x]）？順便說一句，如果你想知道，這是來自算法分析的着名書籍之一。

來源

2009-10-01 halluc1nati0n

不，它需要是and，否則如果沒有找到k，您會解除引用NIL。請記住，只要表達式計算結果爲真，while就會執行。

while x ≠ NIL and k ≠ key[x]

如果x是NIL，則表達式x ≠ NIL and k ≠ key[x]是假的，因爲x ≠ NIL是假的。 and的任一側爲假使得整個表達式爲假。

如果or，替代了，x ≠ NIL仍然是假的，但你需要給對方評價 - 一個or的雙方必須是假的or是假的。不幸的是，評估另一方的解引用NIL。糟糕！即使不是這個問題，k ≠ key[x]是真實的（因爲我們正在考慮找不到k的情況，所以樹x中沒有key可以是k）。由於or的一個（或多個）邊是真的，因此or的計算結果爲true，並且循環將一直持續。

在英語中，雖然可以讀取：在仍然有樹左（x ≠ NIL）和我們還沒有發現我們正在尋找（k ≠ key[x]）。

來源

2009-10-01 06:55:24 derobert

是不是實際需要的OR部分？我的意思是如果你來到x = NIL的部分，就出來並返回x，或者如果你找到了key，那麼再返回並打印x。而不是等待兩者同時發生。我的理解是否正確？ – halluc1nati0n 2009-10-01 07:02:30

編輯：哦，我現在得到它，while循環總是有一個棘手的有點邏輯參數：d 如果我們去到x =零，有或關鍵字時，第k≠鍵[X]仍然會保留，因此while循環仍然會嘗試執行（我們不打算這麼做）。這很有趣，我認爲現在甚至把它當作一個問題，我覺得很愚蠢！ – halluc1nati0n 2009-10-01 07:16:08

二叉樹搜索的迭代版本

回答

相關問題