::: hljs-center

二叉树遍历的应用

:::

利用二叉树遍历的框架,思想可以做很多二叉树应用方面的问题

输出所有叶子节点

将二叉树中所有没有儿子的节点输出,使用先序遍历来做;在先序遍历算法中，增加检测节点的 “左右儿子是否为空”
程序的实现如下

1
2
3
4
5
6
7
8
void PreOrderTraversal(BinTree BT){
	if(BT){
		if(!BT.left&&!BT.right) cout << BT.data << endl; //判断是否左右儿子都为空
		PreOrderTraversal(BT.left);
		PreOrderTraversal(BT.right);
	}

}

求二叉树高度

树使用递归定义，那必然也可以用递归的方式求解这个问题;这个问题实际上是求 “根节点左右子树高度的较大者+1”
之前提到过不同序的区别在于访问节点的时机不同，要求根节点左右子树的高度，那必然是要先递归处理左右子树，最后递归层再返回到根节点

1
2
3
4
5
6
7
8
9
// 求二叉树高度
int PostOrderTraversal(BinTree BT) {
	if(BT){
		int lf = PreOrderTraversal(BT.left); //左子树高度
		int rf = PreOrderTraversal(BT.right);  //右子树高度
		return max(lf,rf)+1;
	}
	return 0;
}

那就是使用后序遍历来做了

二元表达式树

image.png

如图给出的二元表达式树，树当中的叶节点为运算数，非叶节点为运算符号;每一棵子树描述了一个式子。
通过不同的遍历次序可以得到 前缀表达式，中缀表达式，后缀表达式

image.png

如图中缀表达式直接通过前序遍历的方式输出是不准确的，必须在开始递归左子树时输出”(“,并在返回的时候输出右括号”)”
这样才能得到正确的中缀表达式

由两种遍历序列确定一棵唯一二叉树

当得知一棵树的两种遍历序列，是否能推出一棵唯一的二叉树? 答案是 “两种序列中必须包含一个中序”
为什么给出后序，先序的遍历结果不能推测出来呢？例如前序遍历的结果为 AB;后序为BA，并没法知道B是A的左儿子还是右儿子，自然就无法知道二叉树的准确形式了