Go语言实现二叉树的中序遍历（手把手教你掌握数据结构核心算法）

用 Go 语言定义二叉树节点

首先，我们需要定义一个二叉树节点的结构体。在 Go 中，这非常简单：

type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}  

每个节点包含一个整数值 Val，以及指向左右子节点的指针 Left 和 Right。

递归实现中序遍历

最直观的方式是使用递归。思路如下：

1. 如果当前节点为空，直接返回；
2. 递归遍历左子树；
3. 访问当前节点（例如打印值或存入切片）；
4. 递归遍历右子树。

func inorderTraversal(root *TreeNode) []int {    var result []int    var inorder func(*TreeNode)        inorder = func(node *TreeNode) {        if node == nil {            return        }        inorder(node.Left)   // 遍历左子树        result = append(result, node.Val) // 访问根节点        inorder(node.Right)  // 遍历右子树    }        inorder(root)    return result}  

迭代实现中序遍历（使用栈）

虽然递归简洁，但在处理极深的树时可能引发栈溢出。因此，我们也可以用显式栈来实现非递归版本：

func inorderTraversalIterative(root *TreeNode) []int {    var result []int    stack := []*TreeNode{}    current := root        for current != nil || len(stack) > 0 {        // 一直向左走到底，并将路径上的节点入栈        for current != nil {            stack = append(stack, current)            current = current.Left        }                // 弹出栈顶节点        current = stack[len(stack)-1]        stack = stack[:len(stack)-1]                result = append(result, current.Val)                // 转向右子树        current = current.Right    }        return result}  

完整示例与测试

下面是一个完整的可运行示例，包含构建树和调用遍历函数：

package mainimport "fmt"type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func inorderTraversal(root *TreeNode) []int {    var result []int    var inorder func(*TreeNode)    inorder = func(node *TreeNode) {        if node == nil {            return        }        inorder(node.Left)        result = append(result, node.Val)        inorder(node.Right)    }    inorder(root)    return result}func main() {    // 构建如下二叉树：    //       1    //        \    //         2    //        /    //       3    root := &TreeNode{Val: 1}    root.Right = &TreeNode{Val: 2}    root.Right.Left = &TreeNode{Val: 3}    fmt.Println(inorderTraversal(root)) // 输出: [1 3 2]}  

总结

通过本教程，你已经掌握了在Go语言入门阶段如何实现二叉树的中序遍历。无论是递归还是迭代方式，理解其核心思想——“左→根→右”——是关键。这种遍历方式在数据结构教程中属于基础但极其重要的内容，广泛应用于表达式求值、BST验证等场景。

建议你动手敲一遍代码，尝试修改树的结构，观察输出结果的变化。实践是掌握Go语言二叉树的最佳途径！