3

用于在二叉搜索树中搜索节点（值为 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

（迭代算法的）第一行实际上不应该是 while (x ≠ NIL OR k ≠ key[x]) 而不是 (while x ≠ NIL and k ≠ key[x]) 吗？

顺便说一句，如果您想知道，这是来自著名的算法分析书籍之一。

4

1 回答 1

2

不，它必须是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仍然是假的，但你需要评估另一面——an 的两边都or必须是假的，or才会是假的。不幸的是，评估对方取消引用 NIL。哎呀。即使不是因为那个问题，k ≠ key[x]也是真的（因为我们正在考虑没有找到 k 的情况，所以key树中的nox可以是k）。由于 的一侧（或多侧）or为真，因此or计算结果为真，并且循环永远继续。

在英语中，while 可以读作：while 还有树（x ≠ NIL），我们还没有找到我们要找的东西（k ≠ key[x]）。

于 2009-10-01T06:55:24.013 回答