算法与数据结构.ppt

文档介绍：数据结构的分类方式
1
线性结构的分类
2
第五章树和二叉树
二叉树及其ADT
二叉树的周游
二叉树的实现
二叉树的应用
树及其ADT
树的实现
树林
3
线性结构和非线性结构。
树形结构是以分支关系定义的层次结构,在现实世界中广泛存在,在计算机领域中也有广泛应用。
重点
二叉树的存储结构及其各种操作
树和森林与二叉树之间的转换
4
树的表示:树形图
5
(A(B(D)(E(I)(J))(F))(C(G)(H)))
嵌套括号表示法
C
D
E
I
J
F
G
H
A
B
文氏图表示法
6
树型结构
树型结构是一类重要的非线性结构
分支
层次
类似于自然界中的树
树型结构不再是线性,它没有头尾的概念
7
树
更灵活的数据结构
常用的树
二叉树
家谱
公司结构
调用树(程序设计,学期project)
四叉树(平面计算几何)
八叉树(空间计算几何)
任何树都可以用简单的二叉树表示
8
二叉树:
它是结点的有限集合,这个集合或者为空集
或者由一个根及两棵不相交的分别称作这个根
的“左子树”和“右子树”的二叉树组成。
它的每一个结点至多有两棵子树,并且子树
有左右之分,不能随意颠倒。
据定义构造二叉树 0,1,2,3。
二叉树及其ADT
9
二叉树是:
空树
只有根结点
根结点+左子二叉树
根结点+右子二叉树
根结点+左右子二叉树
10