文档介绍：第6章 树和二叉树
前面讲的线性表主要表现的是数据元素之间的前后次序关系，是一种线性结构。
树型结构是以分支关系定义的层次结构。树形结构在客观世界中广泛存在，如人类的家庭族谱及各种社会组织机构。又如计算机文件管理和信息组织也用到树形结构。本章讨论树的基本概念，重点讨论二叉树的有关概念、性质、存储结构和各种运算。
1
树的定义
树(tree)是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有:
(1)仅有一个特殊的结点称为根(root)结点，根结点没有前驱结点；
(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵树，称之为根的子树（ subtree）。
注：树的定义具有递归性，即“树中还有树”。
仅有一个根结点的树是最小树，
树基本概念和术语
2
若干术语
（从结构上分）
分支结点：度不为0的结点，除叶结点之外的其余结点。
A
B
C
G
E
I
D
H
F
J
M
L
K
结点（node）：由数据元素和构造数据元素之间关系的指针组成
结点的度：结点所拥有的子树的个数
树的度：树中所有结点的度的最大值
叶结点：度为0的结点，也称作终端结点
结点的层次：从根结点到树中某结点所经路径上的分支数
树的深度：树中所有结点的层次的最大值
森林：m（m≥0）棵树的集合
3
（从关系上分）
孩子(child)结点：树中一个结点的子树的根结点
双亲(parent)结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点
兄弟(sibling)结点：具有相同的双亲结点的结点
A
B
C
G
E
I
D
H
F
J
M
L
K
4
无序树：树中任意一个结点的各孩子结点之间的次序构成 无关紧要的树
有序树：树中任意一个结点的各孩子结点有严格排列次序的树
若干术语
（从结构上分）
B
E
F
L
K
B
F
E
L
K
5
树的表示形式
(1)倒悬树法(直观表示)
(2)集合包含关系图法
(3)凹入表示法
A
B
C
G
E
I
D
H
F
J
M
L
K
F
E
K
L
C
G
A
B
I
J
M
D
H
A
B
C
D
E
F
G
H
I
J
K
L
M
6
树的抽象数据类型
数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。
操作集合:
（1）创建MakeTree(T)
（2）撤消DestroyTree(T)
（3）双亲结点Parent(T, curr)
（4）左孩子结点LeftChild(T, curr)
（5）右兄弟结点RightSibling(T, curr)
（6）遍历树Traverse(T, Visit())
7
树的存储结构
树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。
指针有常规指针和仿真指针
8
4
H
2
G
1
F
1
E
1
D
0
C
0
B
-1
A
I
4
data parent
0
1
2
3
4
5
6
7
8
(1)双亲表示法
(a)一棵树
（b)仿真指针的双亲表示法存储结构
树及其使用仿真指针的双亲表示法
A
B
C
F
G
E
I
H
D
9
(2)孩子表示法
常规指针的孩子表示法
B
C
root
A
∧
∧
∧
D
∧
∧
∧
E
∧
F
∧
∧
∧
G
∧
∧
∧
I
∧
∧
∧
H
∧
∧
∧
A
B
C
F
G
E
I
H
D
10