software asic puter主讲：赵英良西安交通大学计算.ppt

计算机软件基础
The software basic puter
主讲:赵英良
西安交通大学
计算机教学实验中心
第4单元
非线性数据结构
树、二叉树
6/26/2017
1
上一单元内容提要
一、栈
栈、栈顶指针
顺序存储、共享栈、链栈、入栈、出栈操作
二、队列
队列、顺序存储、队头指针、队尾指针、约定
循环队列、链式队列(带头结点)、入队、出队
三、串
串、长度、空串(空格串)、子串、主串、
位置、子串位置、串相等、串的操作、
串的存储结构、紧缩存储、非紧缩存储
四、数组:行、列优先顺序存储,矩阵的压缩存储
2
一、树型结构及其基本概念
树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在,并应用于:
人类社会的族谱、家谱、行政区域划分管理;
各种社会组织机构;
在计算机领域中,用树表示源程序的语法结构;
在OS中,文件系统、目录等组织结构也是用树来表示的。
西安交大
电信学院
管理学院
医学院
……
信通系
电子系
计算机系
计教中心
……
计01
计02
计12
张三
李四
王五
3
(逻辑结构)
树是一种数据结构:
Tree=(D,R)
其中:
D 是具有相同特性的n个数据元素的集合;
R 是D上逻辑关系的集合,且满足:
在D中存在唯一的称为根的数据元素,没有前趋;
D中其余数据元素都有且只有一个前趋;
D中所有元素,或有若干个互不相同的后继(子树),或无后继(叶结点);
则称Tree为树。
4
树的定义(递归结构)
树是一个或多个结点组成的有限集合T,有一个特定结点称为根,其余结点分为m(m0)个互不相交的集合T1,T2,…,Tm。每个集合又是一棵树,被称为这个根的子树。
树是一种递归结构,可以包含一个结点,该结点包含不相交的树的指针(即子树)。
5

(1) 一般形式
(2) 嵌套形式
(3) 凹入形式
(4) 广义表形式
6
树的表示(一般形式)
A
B
C
D
E
F
K
L
G
H
I
J
M
A
(a)
(b)
(a)只有根结点的树
(b)一般的树
7
树的表示(嵌套形式)
A
C
G
B
F
E
K
L
M
H
D
J
I
8
树的表示(凹入形式)
A
B
E
K
L
C
D
F
G
H
I
J
M
9
树的表示(广义表形式)
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第一层
第二层
第三层
第四层
10