数据结构课件 - 河南大学精品课程网

树的抽象数据类型定义

（见教材P118-119）

ADT Tree{

数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D为空集，则称为空树；//允许n=0

若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root 唯一//关于根的说明

②Dj∩Dk= Φ //关于子树不相交的说明③…… //关于数据元素的说明

基本操作P：//至少有15个}ADT Tree

9

A2. 若干术语

BCDJ根——即根结点(没有前驱)EFGHI叶子——即终端结点(没有后继)森林——指m棵不相交的树的集KLM合(例如删除A后的子树个数)

有序树——结点各子树从左至右有序，不能互换（左为第一）无序树——结点各子树可互换位置。

双亲——即上层的那个结点(直接前驱)

孩子——即下层结点的子树的根(直接后继)

兄弟——同一双亲下的同层结点（孩子之间互称兄弟）堂兄弟——即双亲位于同一层的结点（但并非同一双亲）祖先——即从根到该结点所经分支的所有结点子孙——即该结点下层子树中的任一结点

10

2. 若干术语（续）

结点——即树的数据元素结点的度——结点挂接的子树数

（有几个直接后继就是几度，亦称“次数”）

KBELFACDHMI

JG结点的层次——从根到该结点的层数（根结点算第一层）终端结点——即度为0的结点，即叶子

分支结点——即度不为0的结点（也称为内部结点）

树的度——所有结点度中的最大值（Max{各结点的度}）

树的深度——指所有结点中最大的层数（Max{各结点的层次}）(或高度)

问：右上图中的结点数＝13；树的度＝3；树的深度＝4

11

3. 树的逻辑结构

(特点)：一对多（1:n），有多个直接后继（如家谱

树、目录树等等），但只有一个根结点，且子树之间互不相交。

4. 树的存储结构

讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储等方式。

12