BST遍历中的递归搜索

Question

我对 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 是这棵树中的最后一个节点，所以我们只需要 return 数组，即只有 1 存储在切片中。

到达叶节点 1 后发生了什么，我们如何移动节点 back/upward，例如从 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
}

Answer 1

if tree.Right != nil{ and there is nothing since 1 is the very last node in this tree so we simply have to return array,

这是正确的，但您需要考虑所谓的 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 中尝试。希望能有所帮助；递归可能很难理解，但是有很多 articles/videos 可用（无论语言如何，基本原理都是相同的）。

BST遍历中的递归搜索

Recursive Search in BST Traversal

binary-tree

go

binary-search-tree