- Python编程300例:快速构建可执行高质量代码
- 李永华编著
- 209字
- 2021-03-26 23:33:25
例69 完全二叉树
1.问题描述
完全二叉树的特点是:只允许最后一层有空缺节点且空缺在右边,即叶子节点只能在层次最大的两层上出现;对任一节点,如果其右子树的深度为j,则其左子树的深度必为j或j+1,即度为1的点只有1个或0个。判断一个二叉树是否是完全二叉树。
2.问题示例
输入二叉树为{1,2,3,4},输出True,如下所示是完全二叉树。
![](https://epubservercos.yuewen.com/E3EF07/19549640501519606/epubprivate/OEBPS/Images/Figure-P84_24795.jpg?sign=1739418420-GApuJtiiKBSeNbNvdbNrUcbvrQVDmFHv-0-c06178100f93c5ad959e0312f2eaf355)
输入{1,2,3,#,4},输出False,如下所示不是完全二叉树。
![](https://epubservercos.yuewen.com/E3EF07/19549640501519606/epubprivate/OEBPS/Images/Figure-P84_24797.jpg?sign=1739418420-WM6jRDtOyf0kMLbSEb0rGGtdMuDg0mzA-0-9f70b2486bb020b2ffd59a1f19b1ece1)
3.代码实现
![](https://epubservercos.yuewen.com/E3EF07/19549640501519606/epubprivate/OEBPS/Images/Figure-P84_24799.jpg?sign=1739418420-nwx6Rl0n3QY9BHyAxUzt1CF2zzBozWWq-0-36e92338a7f269bc409a3c2f61b12200)
4.运行结果
输入:1 2 3 4
输出:True