文档介绍：树与二叉树
非线性数据结构
元素结点之间存在分支和层次关系。(一对多)
应用:家谱
社会组织机构
书的章节划分
操作系统中的多级目录结构
高级语言中源程序的语法结构等。
什么是树?
1
第二章常用数据结构及其运算
树与二叉树
树的定义及其存储结构
树的定义(递归定义)
树是由n(n≥0)个结点组成的有限集合T:
有且仅有一个结点称为根结点(root)
其余结点分为m(m≥0)个各互不相交的有限集合 T1、T2、…、Tm,其中每一个集合Ti本身又是 一棵树,称为根结点root的子树。
n=0时,为空树。
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
2
第二章常用数据结构及其运算
树的定义及其存储结构
树与二叉树
2. 常用术语
1)结点:表示树中的元素。
2)度:结点拥有的子树数。如A的度为3,B 的度为2。树的度=树中最大的结点度数。
3)叶子(终端结点):度为0的结点。
4)孩子:结点的子树的根(后继结点)。每个结点均是其前驱结点的孩子。
5)双亲:一个结点的前驱结点。
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
1
2
3
4
3
第二章常用数据结构及其运算
树的定义及其存储结构
树与二叉树
6)子孙:以某结点为根的子树中的任一结点。
7)祖先:从根到该结点所经分支上的所有结点。
8)兄弟:同一双亲的孩子。
9)结点的层次:根为第一层,根的直接后继结点为第二层,以此类推。
10)深度:树中结点的最大层次数。
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
1
2
3
4
4
第二章常用数据结构及其运算
树的定义及其存储结构
树与二叉树
11)森林:是m(m≥0)棵互不相交的树的集合
12)有序树:树中结点在同层中按从左到右有序排列、不能互换的称为有序树;反之称为无序树。
例:
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
1
2
3
4
A
B
C
T1
A
C
B
T2
有序树:T1!=T2
无序树:T1=T2
5
第二章常用数据结构及其运算
树与二叉树
树的定义及其存储结构
例:用有序树表示算术表达式
(A+B)×5 / (2×(C-D))
/
*
*
+
5
A
B
2
-
C
D
6
第二章常用数据结构及其运算
树的定义及其存储结构
树与二叉树
3. 树的存储结构(链式)
结点的结构类型:
1) 异构型-根据结点的度数设置相应的指针域。
特点:节省空间、运算不便。
2) 同构型-每个结点的指针域个数均为树的度数。
特点:运算方便、浪费空间。
· A · ·
· B · ^
^ E ^ ^
^ F ^ ^
^ C ^ ·
^ D ^ ^
^ G ^ ^
例(空链域问题):一棵具有n个结点的k叉树,采用同构型存储结构,问有多少个空链域?
解:总链域=nk;非空链域=n-1;
所以,空链域=n(k-1)+1。
若树度为k, k=1为线性表,k=2时空链域最低,即二叉树。
7
第二章常用数据结构及其运算
树与二叉树
二叉树及其性质
1. 二叉树的定义及其存储结构
二叉树是n(n≥0)个结点的有限集合,它或为空 树(n=0), 或由一个根结点和两棵分别称为左子树和右子树的互不 相交的二叉树构成。(递归定义。) 即:度<=2的有序树
特点:每个结点至多有2个孩子,结点度数最大为2;
结点子树有左右之分。
存储结构:采用二叉链表存储。
B
A
D
F
E
C
A ^
B
^ F ^
^ E ^
D
^ C ^
Data
Lchild
Rchild
结点结构:
8
第二章常用数据结构及其运算
树与二叉树
二叉树及其性质
1. 二叉树的定义及其存储结构
二叉树的五种形态
A
A
B
A
B
A
B
C
思考:二叉树与二叉有序树的区别?
二叉树可以是空的,而二次有序树至少有一个结点的度为2。
9
第二章常用数据结构及其运算
树与二叉树
2. 二叉树的基本性质
二叉树的第i层上至