文档介绍：计算机软件技术基础
教师:曾晓东
电话:**********
E_mail: zengxiaodong@
非线性结构
逻辑特征:一个结点可能有多个直接前驱和直接后继。
类型:树型结构、图形结构。
计算机软件技术基础
第四章树形结构
第四章树形结构
树型结构是一类很重要的非线性数据结构,在这类结构中,元素结点之间存在明显的分支和层次关系。
树型结构在客观世界中广泛应用,例如家族关系中的家谱、各种社会组织机构、一本书中的章节划分、操作系统中的多级目录结构、高级语言中源程序的语法结构等。
本章主要讨论树及二叉树的定义及其存储结构,重点讨论二叉树的特性以及应用。
计算机软件技术基础
第四章树形结构
第四章树形结构
一、树的基本概念及存储结构
二、二叉树
三、二叉树的操作
四、树、森林与二叉树的关系
五、二叉排序树
六、哈夫曼树与哈夫曼算法
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
1、树的定义和术语
树的定义
1)定义:树是由n(n≥0)个结点组成的有限集合T,其中有且仅有一个结点称为根结点(root),其余结点可以分为m(m≥0)个各互不相交的有限集合T1、T2、…、Tm,其中每一个集合Ti本身又是一棵树,称为根结点root的子树。当n=0时称为空树。
2)树是一种具有递归性质的结构。
3)树的根结点没有直接前驱,其余结点有且仅有一个直接前驱,所有结点可以有0个或多个直接后继。
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
常用术语
1)结点:表示树中的元素。如A、B、K等
2)度:结点拥有的子树数。如A的度为3,C的度为1。一棵树中最大的结点度数为这棵树的度。上图中树的度为3。
3)叶子:度为0的结点,又称终端结点,如K、L、G等。
4)孩子:结点的子树的根,如B、C、D均是A的孩子。
5)双亲:相应地,该结点称为孩子的双亲,如A是B、C、D的双亲
A
B
D
K
E
F
L
M
J
I
H
G
C
T1
T2
T3
root
1
2
3
4
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
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
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
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
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
2、树的存储结构
1)树是多分支非线性表,因此需要采用多重链表结构,即每个结点设有多个指针域,其中每一个指针指向一棵子树的根结点。如图:
· A · ·
· B · ^
^ E ^ ^
^ F ^ ^
^ C ^ ·
^ D ^ ^
^ G ^ ^
2)结点异构型和结点同构型。
结点异构型:不定长度结点的多重链表
省空间,但运算复杂
结点同构型:采用定长度结点的多重链表,均按树的度数设指针域
运算方便,但有许多域为空,浪费空间
计算机软件技术基础
第四章树形结构
一、树的基本概念及存储结构
3)空链域问题:假设有一棵具有n个结点、度为k的树,采用同构型存储结构,那么有多少个空链域?
总链域=n*k;
考虑每个结点只有一个双亲,因此指向该结点的指针只有一个,但根结点无双亲,因此无指针指向它
非空链域=n-1;
所以,空链域=n(k-1)+1。
解决方法:转化为二叉树
· A · ·
· B · ^
^ E ^ ^
^ F ^ ^
^ C ^ ·
^ D ^ ^
^ G ^ ^
计算机软件技术基础
第四章树形结构