Pseudocode-搜索树

Question

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

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

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

1) def findval (node，lookForElement):< br > 2)while node不为空:< br> 3)如果node.val等于lookForElement:< br > 4)break < br > 5)如果node.val小于lookForElement:< br > 6)node = node . right < br > 7)else:< br > 8)node = node . left < br > 9)返回node 10)如果node为空:11)打印“树为空”

但是我认为这只有在被搜索的元素是下一个元素的情况下才有效，但是被搜索的元素可能是下几个分支，那么我如何正确地循环呢？

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

缩进和空格使得return语句应该在WHILE循环之外变得更加清楚。你只能通过打破循环来达到它，这发生在你已经找到搜索值的时候(万岁！)，或者当节点变为空时。如果node为空，那么我们需要的值不在树中。

使用以下树：

      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”为空，或者从循环内部返回。但是在循环中，每次我们向下移动一个节点，首先我们检查它是否为空，如果是，我们插入并返回。所以“节点”的值唯一可以为空的时候是根为空的时候。