19.3 二叉树的遍历

19.3 二叉树的遍历

链表的遍历方法显而易见：从前到后遍历即可。而二叉树是一种树状结构，可以采用深度优先策略的遍历算法，比如前序遍历(Pre-order Traversal)、中序遍历(In-order Traversal)和后序遍历(Post-order Traversal)。也可以采用广度优先策略的遍历算法，比如层序遍历(Level-order Traversal)。

前序遍历：

1> 访问根节点
2> 递归遍历左子树
3> 递归遍历右子树

void pre_order(link t, void (*visit)(link))
{
	if (!t)
		return;
	visit(t);
	pre_order(t->l, visit);
	pre_order(t->r, visit);
}

中序遍历：

1> 递归遍历左子树
2> 访问根结点
3> 递归遍历右子树

void in_order(link t, void (*visit)(link))
{
	if (!t)
		return;
	in_order(t->l, visit);
	visit(t);
	in_order(t->r, visit);
}

后序遍历

1> 递归遍历左子树
2> 递归遍历右子树
3> 访问根结点

void post_order(link t, void (*visit)(link))
{
	if (!t)
		return;
	post_order(t->l, visit);
	post_order(t->r, visit);
	visit(t);
}