Page 109 - 高中 信息技术 选择性必修1 数据与数据结构

 4.3 用抽象数据类型表示二叉树

在二叉树中，每个结点的左子树的根结点被称为左孩子，右子树的根结点被称为右孩
子。二叉树有五种基本形态，如图4-10所示。

图4-10 二叉树的五种基本形态
（a）为空二叉树；（b）为仅有根结点的二叉树；（c）为右子树为空的二叉树；（d）为

左右子树均非空的二叉树；（e）为左子树为空的二叉树。

k
一棵深度为k且有2 -1个结点的二叉树称为满二叉树，如图4-11（a）所示。在一棵二
叉树中，除最后一层外，若其余各层都是满的，并且最后一层或者是满的，或者是在右边

缺少连续若干个结点，则称此树为完全二叉树，如图4-11（b）所示。满二叉树是完全二
叉树的特例。 广东教育出版社

（a）满二叉树 （b）完全二叉树

图4-11 满二叉树和完全二叉树

4 . 3 . 3 二叉树的抽象数据类型

二叉树的抽象数据类型的数据部分为一棵用任一种方式表示的二叉树，操作部分包括
初始化二叉树、建立二叉树、遍历二叉树、查找二叉树、输出二叉树和清除二叉树等常用
操作。下面给出二叉树的抽象数据类型的参考定义：

ADT 二叉树
{
数据：采用任一种方式存储的二叉树，其存储类型用BinTreeType标识符表

示，该类型的一个二叉树用BT标识符表示。二叉树结点所保存的数据元素类

101101

21X2204.indd 101 2019/9/26 13:53:27