1.输出二叉树的叶子结点
这里,我们首先需要明白叶子结点的定义:左右子树是否都为空,接下来,用代码来实现就变得简单啦。即:我们只需要在二叉树的遍历算法中增加检测结点的"左右子树是否都为空"即可。具体代码如下:
/**
* 前序遍历二叉树操作
* 在每次遍历结点之前,首先判断其左子树和右子 树是否都为空
*/
void preOrderPrintLeaves(BinTree BT){
if(BT){
if(!BT -> Left && ! BT -> Right){
printf("%d",BT -> Data);
}
PreOrderPrintLeaves(BT -> Left);
PreOrderPrintLeaves(BT -> Right);
}
}
// 再次强调,这里的if(BT) 等价于 if(BT != NULL)
2.求二叉树的高度
二叉树是递归定义的,所以二叉树的高度也可以考虑用递归来实现。首先我们来分析一下:结点和其左右结点的关系。我们可以发现 :
Height = max{LeftHeight,RightHeight}+1
树的高度与其左右子树高度的关系
很显然,我们要想知道二叉树的高度,必须要先知道其左右子树的高度。这样的话,我们显然应该采用后序遍历的基本逻辑来实现该功能。
// 改造后序遍历
int PostOrderGetHeight(BinTree BT){
int HL; // 左子树高度
int HR; // 右子树高度
int MaxH; // 最大高度
if(BT){
HL = PostOrderGetHeight(BT -> Left);//递归求左子树的高度
HR = PostOrderGetHeight(BT -> Right);//递归求右子树的高度
MaxH = (HL > HR) ? HL : HR ;// 取两者的最大值
return (MaxH + 1); // 返回树的深度
}
return 0; // 空树的深度为 0
}
3. 二元运算表达式树及其遍历
二元表达式观察上图可以知道:叶子结点都是操作数,而其他结点都是运算符号;
采用三种遍历方式会得到三种不同的访问结果:
- 先序遍历 -> 前缀表达式:+ + a * b c * + * d g f e ;
- 中序遍历 -> 中缀表达式:a + b * c + d * e + f * g ;
- 后序遍历 -> 后缀表达式:a b c * + d e * f + g * + ;
由中序遍历得到的中缀表达式会受到运算符优先级的影响
如何解决中序遍历的中缀表达式不准的问题呢? 答案是:通过访问左子树之前加入左括号,而访问右子树之前添加右括号的形式来保证得到正确的中缀表达式。即:通过加括号的形式来保证运算符的优先级;
4.由两种遍历序列确定二叉树
问题描述:已知三种遍历中的任意两种遍历序列,能否唯一确定一颗二叉树呢?
必须要中序遍历才可以。没有中序遍历序列,我们只能确定根节点,而无法确定左右子树的关系。
先序和中序来确定一棵二叉树
分析过程:
- 根据先序遍历序列的第一个结点确定根结点;
- 根据根结点在中序遍历序列中分割出左右子两个子序列;
- 对左子序列和右子序列分别递归使用相同的方法继续分割
网友评论