数据结构（六）：树

树的定义

1. 树的定义

• 树是 n ( n >= 0 ) 个结点的有限集，n = 0 时称为空树
• 任意一棵非空树中，有且仅有一个根结点
• 当 n > 1 时，其余结点分为 m（m > 0）个互不相交的有限集

P6Z2d.png

2. 结点概念

• 结点：树的结点包含一个数据元素及若干个指向子树的分支
• 结点的度：结点拥有的子树
• 叶子结点：度为 0 的结点
• 分支结点：度不为 0 的结点
• 内部结点：除根结点以外，分支结点也称为内部结点
• 树的度：树内各结点的度的最大值
• 树的深度：树中结点最大层次称为树的深度

3. 结点之间的关系

• 结点的父结点称为双亲（Parent）
• 同一个父结点的子结点之间称为兄弟结点（sibling）
• 无序树和有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该数为有序树，否则为无序树

4. 树的抽象数据类型

• Data（数据元素）：树是由一个根结点和若干棵子树构成，树中结点具有相同的数据类型及层次关系
• 基本操作

方法	描述
InitTree(*T)	构造空树 T
DestoryTree(*T)	销毁树 T
ClearTree(*T，definition)	按 definition 中给出的树定义来构造树
ClearTree(*T)	若树 T 存在，则将树 T 清为空树
TreeEmpty(T)	若 T 为空树返回 true，否则 false
TreeDepth(T)	返回 T 的深度
Root(T)	返回 T 的根结点
Value(T,cur_e)	cur_e 是树 T 中一个结点，返回此结点的值
Assign(T,cur_e,value)	给树 T 的结点 cure_e 赋值为 value
Parent（T,cur_e）	若 cur_e 是树 T 的非根结点，则返回它的双亲，否则返回空
LeftChild(T,cur_e)	若 cur_e 是树 T 的非叶结点，则返回它最左的子结点，否则返回空
RightSibling(T,cur_e)	若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空
InsertChild(T,p,i,c)	其中 p 指向树 T 的某个结点，i 为所指结点 p 的度加上 1，非空树 c 与 T 不想交，操作结果为插入 c 为 树 T 中 p 指结点的第 i 棵子树
DeleteChild(T,p,i)	其中 p 指向树 T 的某个结点，i 为所指结点 p 的度，操作结果为删除 T 中 p 所指结点的第 i 棵子树

树的顺序存储

简单的顺序存储结构是不能满足树的实现要求的，需要充分利用顺序存储和链式存储结构的特点，如何表示树与其子树之间的关系，主要有三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法

1.双亲表示法

每个结点除了知道自己是谁以外，还要知道其双亲结点（Parent），通过结点的 parent 找到其父结点，时间复杂度为 O(1)，直到 parent 为 -1 时，表示找到了树的根，根结点没有双亲，所以根结点的位置域为 -1

双亲表示法结构

data（数据域）	parent（指针域）
存储结点的数据信息	存储该结点的双亲所在数组中的下标

P6p1A.png

双亲表示法的子结点与兄弟结点

• 要知道结点的子结点，可以增加一个长子域，它指向结点最左边的子结点

长子域

• 要知道结点的兄弟结点，可以增加一个右兄弟域，它指向某子结点右边的结点，若右兄弟不存在，则赋值为 -1

兄弟域

2.孩子表示法

把每个结点的子结点排列起来，以单链表作为存储结构，n 个结点有 n 个子结点链表，如果是叶子结点则此单链表为空，然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中

孩子表示法结构

• 子结点链表的子结点

child（数据域）	next（指针域）
存储某个结点在表头数组中的下标	存储指向某结点的下一个孩子结点的指针

• 表头数组的表头结点

data（数据域）	firstchild（头指针域）
存储某个结点的数据信息	存储该结点的孩子链表的头指针

3.孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此我们设置两个指针，分别指向该结点的第一个子结点和此结点的右兄弟

孩子兄弟表示法结构

data（数据域）	firstchild（指针域）	rightchild（指针域）
存储结点的数据信息	存储该结点的第一个孩子的存储地址	存储该结点的右兄弟结点的存储地址

PlWM9.png