二叉树搜索的迭代版本

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

二叉树搜索的迭代版本

回答

相关问题