中序遍历

树

说明

按左、根、右访问；二叉搜索树得到有序序列。

分析

先递归左子树，再访问当前节点，最后递归右子树。对于满足左小右大的二叉搜索树，得到的值自然升序排列。

以根2、左1、右3为例，访问顺序为1,2,3。升序来自搜索树约束；普通二叉树的中序不会自动排序。每个节点访问一次；递归栈随树高变化，层序队列峰值则受层宽影响。

查看图表代码

适用前提与边界

普通二叉树并不具备这个有序性质，遍历顺序本身不会排序数据。 输入必须是无环二叉树；递归空间为O(h)，退化链高度可达n，只有搜索树才保证输出有序。

示例输入与调用

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

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

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

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

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