伪代码——搜索树

Question

我需要一些帮助来解决以下问题。有一个搜索树（二叉搜索树），我需要找到一个特定的元素，所以要搜索搜索树。但这只需要在伪代码中显示（所以不需要实际的搜索树，所以只是举个例子根是75，需要搜索的元素是24）。

例如，第 1 步：打印根，第 2 步：打印树....（直到找到正确的元素）。

到目前为止我已经这样做了：

1) def findval (node, lookForElement):
2）当节点不为空时：
3) 如果 node.val 等于 lookForElement:
4) 中断
5) 如果 node.val 小于 lookForElement:
6）节点=node.right
7) 其他:
8）节点=node.left
9) return 节点 10) 如果节点为空： 11) 打印 "tree is empty"

但我认为这仅在搜索到的元素是下一个向下元素时才有效，但搜索到的元素可能向下几个分支，因此我该如何正确循环？

Answer 1

您找到节点的算法非常正确：

DEF FINDVAL(search)
  LET node = root
  WHILE node != null
    PRINT_ELEMENTS(node)
    IF node.value == search
      BREAK
    ELSE IF node.value < search
      node = node.right
    ELSE
      node = node.left

  RETURN node

缩进和 space 使 return 语句应该在 WHILE 循环之外更清楚。您只能通过跳出循环来到达它，这发生在您找到搜索值（万岁！）或节点变为空时。如果节点为空，那么我们想要的值不在树中。

具有以下树：

      75
    /    \
   18    88
  /  \     \
 6   24    90

FINDVAL 算法将显示以下内容：

6, 18, 24, 75, 88, 90
6, 18, 24
24

更新：要插入一个新值，如果它不存在的话：

DEF INSERTVAL(value)
  LET node = root
  WHILE node != null
    PRINT_ELEMENTS(node)
    IF node.value == value
      PRINT("Value already exists")
      RETURN
    ELSE IF node.value < value
      IF node.right == null
        node.right = new Node(value)
        RETURN
      node = node.right
    ELSE
      IF node.left == null
        node.left = new Node(value)
        RETURN
      node = node.left

  root = new Node(value)

这个伪代码可能看起来有点难以理解，因为我们必须一次查看树中的两层，而不是一层。我们查看父级，决定是向左还是向右，然后如果该方向为空，我们将插入新值。如果它不为空，我们继续到该节点并重复。

现在，退出 while 循环的唯一方法仍然是 'node' 为 null，或者我们 return 从循环中退出。但是在循环中，每次我们向下移动一个节点时，首先我们检查它是否为空，如果是，我们插入 and return。所以 'node' 的值唯一可以为空的情况是根为空。

伪代码——搜索树

Pseudocode - Search Tree

search

loops

pseudocode

binary-search

binary-search-tree