抽象数据类型

2025年11月27日

版权

第四章　抽象数据类型

一、认识抽象数据类型

抽象数据类型是指由一种数据结构和在其上的一组操作所组成的、并不具体关心数据的存储结构和操作的具体实现的抽象数据结构。

定义抽象数据类型的基本格式：

ADT 抽象数据类型名

　｛

　数据：<数据描述>

　操作：<基本操作的定义>

　｝ADT 抽象数据类型名

例如，长方形可以抽象为（以Python为例）：

class rectangle（object）：

　　def __init__（self，a，b）：

　　　　self.a=a

　　　　self.b=b

　def area（self）：

　　　　s=self.a*self.b

　　　　return s

　　def perimeter（self）：

　　　　c=2*self.a+2self.b

　　　　return c

二、用抽象数据类型表示队列和栈

1.用抽象数据类型表示队列

ADT 队列

　　｛数据：

　　　　队列元素；

　　　　队头；

　　　　队尾；

　　　操作：

　　　　初始化；

　　　　入队；

　　　　出队；

　　　　求长度；

　　　　判断空；

　　　　判断满；

　　｝ADT 队列

2.用抽象数据类型表示栈

ADT 栈

　　｛数据：

　　　　栈元素；

　　　　栈顶；

　　　　栈底；

　　　操作：

　　　　初始化；

　　　　入栈；

　　　　出栈；

　　　　判断空；

　　　　判断满；

　　｝ADT 栈

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

1.树的定义

树是n（n≥0）个节点的有限集。在任意一棵非空树中：①有且仅有一个特定的称为根的节点；②当n＞1时，其余节点分为m（m>0）棵互不相交的有限子树，每棵子树又是一棵树。

2.树的基本概念

（1）节点的度：每个节点具有的子树数。

（2）分支节点和叶子节点：在一棵树中，度等于0的节点称为叶子节点，度大于0的节点称为分支节点或非终端节点。

（3）孩子节点、双亲节点、兄弟节点：在一棵树中，每个节点的子树的根，称为该节点的孩子节点，相应地，该节点被称为孩子节点的父节点。具有同一父节点的孩子节点互称兄弟节点。

（4）树的深度：树中所有节点的最大层数。

3.二叉树的定义

二叉树是一种特殊树形结构，它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），而且二叉树的子树有左右之分，其次序不能任意颠倒。

在二叉树中，每个节点的左子树的根节点被称为左孩子，右子树的根节点被称为右孩子。二叉树有5种基本形态，如下图所示。

一棵深度为k且有2k-1个节点的二叉树称为满二叉树。在一棵二叉树中，除最后一层外，若其余各层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个节点，则称此树为完全二叉树。满二叉树是完全二叉树的特例。

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

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

5.二叉树的遍历

若用L、D、R分别表示遍历左子树、访问根结点、遍历右结点，则对于一棵非空二叉树的遍历有DLR、DRL、LDR、LRD、RDL、RLD六种情况。若限定先左后右，则只有三种情况即DLR（前序遍历）、LDR（中序遍历）、LRD（后序遍历），如图所示。给定了二叉树的任何一种遍历序列，都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列，就可以唯一地确定二叉树。