树的遍历是指按一定顺序访问树中所有节点的过程。常见的树遍历方式主要有以下几种：
1. 前序遍历（Pre-order Traversal）
访问顺序：根节点 → 左子树 → 右子树
特点：
- 先访问根节点，再递归遍历左子树和右子树。
- 可以用来复制树结构。
递归实现：
func preOrderTraversal(root *TreeNode) {
if root == nil {
return
}
fmt.Println(root.Val) // 访问根节点
preOrderTraversal(root.Left) // 递归遍历左子树
preOrderTraversal(root.Right) // 递归遍历右子树
}非递归实现：
func preOrderTraversal(root *TreeNode) {
if root == nil {
return
}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.Val) // 访问根节点
if node.Right != nil {
stack = append(stack, node.Right) // 先入栈右子树
}
if node.Left != nil {
stack = append(stack, node.Left) // 后入栈左子树
}
}
}2. 中序遍历（In-order Traversal）
访问顺序：左子树 → 根节点 → 右子树
特点：
- 先递归遍历左子树，再访问根节点，最后递归遍历右子树。
- 中序遍历二叉搜索树时，会得到一个有序的数列。
递归实现：
func inOrderTraversal(root *TreeNode) {
if root == nil {
return
}
inOrderTraversal(root.Left) // 递归遍历左子树
fmt.Println(root.Val) // 访问根节点
inOrderTraversal(root.Right) // 递归遍历右子树
}非递归实现：
func inOrderTraversal(root *TreeNode) {
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]
fmt.Println(current.Val) // 访问根节点
current = current.Right
}
}3. 后序遍历（Post-order Traversal）
访问顺序：左子树 → 右子树 → 根节点
特点：
- 先递归遍历左子树，再递归遍历右子树，最后访问根节点。
- 常用于删除树，确保在删除父节点前删除子节点。
递归实现：
func postOrderTraversal(root *TreeNode) {
if root == nil {
return
}
postOrderTraversal(root.Left) // 递归遍历左子树
postOrderTraversal(root.Right) // 递归遍历右子树
fmt.Println(root.Val) // 访问根节点
}非递归实现：
func postOrderTraversal(root *TreeNode) {
if root == nil {
return
}
stack1 := []*TreeNode{root}
stack2 := []*TreeNode{}
for len(stack1) > 0 {
node := stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
stack2 = append(stack2, node)
if node.Left != nil {
stack1 = append(stack1, node.Left) // 先入栈左子树
}
if node.Right != nil {
stack1 = append(stack1, node.Right) // 后入栈右子树
}
}
for len(stack2) > 0 {
node := stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
fmt.Println(node.Val) // 访问根节点
}
}4. 层次遍历（Level-order Traversal）
访问顺序：逐层访问，每层从左到右
特点：
- 层次遍历通常使用队列来实现。
- 常用于查找树的最短路径、最宽层等。
实现：
func levelOrderTraversal(root *TreeNode) {
if root == nil {
return
}
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node.Val) // 访问根节点
if node.Left != nil {
queue = append(queue, node.Left) // 入队左子树
}
if node.Right != nil {
queue = append(queue, node.Right) // 入队右子树
}
}
}总结
- 前序遍历：用于前置操作，如复制树、表达式树的输出。
- 中序遍历：特别适合二叉搜索树，用于得到有序序列。
- 后序遍历：用于后置操作，如删除节点。
- 层次遍历：常用于查找问题，逐层扫描节点。