5.2.1.1 几种特殊的二叉树

教材导航 · 第5章

原书定位

印刷页P130起,对应PDF第142页。下文为目视整理的知识提要;完整内容见原书对照。

类型定义与判别
满二叉树高 hh,每层结点达到最大,共 2h−12^h-1 个
完全二叉树按层从左到右填充,只有最后一层可不满且集中在左侧
二叉排序树 BST左子树关键字小于根,右子树大于根,子树递归满足
平衡二叉树 AVL任意结点左右子树高度差绝对值不超过 1
正则二叉树只有度为 0 和 2 的结点,无单孩子结点

满二叉树必为完全二叉树;正则二叉树未必满,也未必完全。完整判别条件要按本书定义,避免只凭图形外观。

图5.3 满二叉树与完全二叉树

图5.3 满二叉树与完全二叉树,原书P131。

对应练习

5.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P130,PDF第142页

原书对照,原书P131,PDF第143页