树的抽象数据类型定义
（见教材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
