用递归在BST中查找节点

本篇文章给大家分享《用递归在BST中查找节点》，覆盖了Golang的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

我对 golang 中的二叉搜索树（bst）遍历解决方案的结构感到困惑。例如，当我们想要从下面的树中获取 inordertraverse 输出时，输出应该是 [1, 2, 5, 5, 10, 15, 22]。

10            
       /    \
      5      15
     / \       \
    2   5       22
   /
  1

我们将首先通过 if tree.left !=nil 检查左树，以便我们可以到达叶节点（在本例中为 1）。由于叶子节点是 tree.left == nil，我们只需将值附加到切片 `array =append(array, tree.value)。

我的困惑来自这里，我们现在站在叶节点 1 处，下一个代码是检查当前节点 if tree.right != nil{ 中是否存在正确的节点，并且自 1 以来没有任何内容是这棵树中的最后一个节点，因此我们只需返回数组，即切片中仅存储 1。

到达叶节点 1 后发生了什么，以及如何将节点向后/向上移动，例如从 1 到 2 或 2 到 5。我真的很困惑递归函数是如何工作的......

type BST struct {
    Value int

    Left  *BST
    Right *BST
}

func (tree *BST) InOrderTraverse(array []int) []int {
    if tree.Left != nil {
        array = tree.Left.InOrderTraverse(array)
    }   

    array = append(array, tree.Value)
    if tree.Right != nil {
        array = tree.Right.InOrderTraverse(array)
    }
    return array
}

解决方案

if tree.right != nil{ 并且没有任何内容，因为 1 是这棵树中的最后一个节点，所以我们只需返回数组，

这是正确的，但您需要考虑所谓的 inordertraverse，因为这决定了 return 之后恢复执行的位置。在本例中，它是从 inordertraverse （对于值为 2 的节点）调用的，因此下一步是 array =append(array, tree.value) （其中 tree.value 为 2），然后检查节点右分支（该节点上没有任何内容，但它将 return 到节点 5 并找到正确的分支）。

如果我们添加一些输出来显示正在检查的级别以及到达该级别所遵循的路径，这可能会更容易理解：

func (tree *bst) inordertraverse(level int, path string, array []int) []int {
    fmt.printf("level %d, path %s\n", level, path)
    if tree.left != nil {
        array = tree.left.inordertraverse(level +1, path + "l", array)
    }

    array = append(array, tree.value)
    if tree.right != nil {
        array = tree.right.inordertraverse(level +1, path + "r", array)
    }
    fmt.printf("done at level %d, path %s\n", level, path)
    return array
}

这将输出：

level 1, path 
level 2, path L
level 3, path LL
level 4, path LLL
Done at level 4, path LLL
Done at level 3, path LL
level 3, path LR
Done at level 3, path LR
Done at level 2, path L
level 2, path R
level 3, path RR
Done at level 3, path RR
Done at level 2, path R
Done at level 1, path

在 playground 中尝试一下。希望这会有所帮助；递归可能很难让您理解，但是有大量的文章/视频可用（无论语言如何，基本原理都是相同的）。

以上就是《用递归在BST中查找节点》的详细内容，更多关于的资料请关注golang学习网公众号！