5.2.1.1 几种特殊的二叉树
原书定位
印刷页P130起,对应PDF第142页。下文为目视整理的知识提要;完整内容见原书对照。
| 类型 | 定义与判别 |
|---|---|
| 满二叉树 | 高 ,每层结点达到最大,共 个 |
| 完全二叉树 | 按层从左到右填充,只有最后一层可不满且集中在左侧 |
| 二叉排序树 BST | 左子树关键字小于根,右子树大于根,子树递归满足 |
| 平衡二叉树 AVL | 任意结点左右子树高度差绝对值不超过 1 |
| 正则二叉树 | 只有度为 0 和 2 的结点,无单孩子结点 |
满二叉树必为完全二叉树;正则二叉树未必满,也未必完全。完整判别条件要按本书定义,避免只凭图形外观。

图5.3 满二叉树与完全二叉树,原书P131。
对应练习
关联知识
原书对照
展开原书对照截图

