11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？

【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。 ⑵ 中序序列和后序序列相同。 ⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。 ⑵ 空二叉树、只有一个根结点的二叉树和左斜树。 ⑶ 空二叉树、只有一个根结点的二叉树

13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。

【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。

精选

14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。

【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下：

15．设计算法，判断一棵二叉树是否为完全二叉树。

【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足：

⑴ 若某结点没有左孩子，则其一定没有右孩子； ⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。

若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。 具体算法如下：

精选