前序遍历

树

说明

按根、左、右访问二叉树；适合复制树结构。

分析

先处理当前节点，再递归左子树和右子树。若把每个节点的值连同结构标记输出，前序顺序可用于序列化或复制树。

以根2、左1、右3为例，访问顺序为2,1,3。仅输出值不能唯一恢复任意二叉树，序列化还需空孩子等结构标记。每个节点访问一次；递归栈随树高变化，层序队列峰值则受层宽影响。

查看图表代码

适用前提与边界

递归实现清晰，但极深的树会增加调用栈；也可以用显式栈迭代。 输入必须是无环二叉树；空树不输出元素，递归栈最坏O(n)，仅有值序列不足以恢复结构。

示例输入与调用

root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	var out []int
	Preorder(root, &out)
	fmt.Println(out)

运行输出

[2 1 3]

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func Preorder(n *Node, out *[]int) {
	if n == nil {
		return
	}
	*out = append(*out, n.Value)
	Preorder(n.Left, out)
	Preorder(n.Right, out)
}

func main() {
	root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	var out []int
	Preorder(root, &out)
	fmt.Println(out)
}