数据结构与算法第5章课后答案(3)

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

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

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

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

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

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

中的较大者。具体算法如下：

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

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

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

若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次

对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否

均有左右孩子，CM存放局部判断结果及最后的结果。 具体算法如下：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构与算法第5章课后答案(3)在线全文阅读。