1 / 100
文档名称:

数据结构PPT教学课件-第六章 树和二叉树.ppt

格式:ppt   页数:100页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构PPT教学课件-第六章 树和二叉树.ppt

上传人:3346389411 2013/4/11 文件大小:0 KB

下载得到文件列表

数据结构PPT教学课件-第六章 树和二叉树.ppt

文档介绍

文档介绍:数据结构
----树和二叉树
第六章树和二叉树
树的定义
1.
二叉树
2.
遍历二叉树
3.
树和森林
4.
赫夫曼树及其应用
5.

树的定义
树:n(n≥0)个结点的有限集合。当n=0时,称为空树;任意一棵非空树满足以下条件:
⑴有且仅有一个特定的称为根的结点;
⑵当n>1时,除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。
树的定义是采用递归方法
A
B
C
D
E
F
G
H
I
J
M
K
L
A( )
T1
T3
T2
树根
例如:
B(E, F(K, L)),
C(G),
D(H, I, J(M))
(a) 一棵树结构(b)一个非树结构(c)一个非树结构
树的定义
A
C
B
G
F
E
D
H
I
A
C
B
G
F
D
A
C
B
G
F
D
E
树的应用举例——文件结构
puter
C:
D:
E:
etc
WINDOWS
Program Files
Picture
Music
……
……
……
……
……
……
……
……
基本术语
结点:
结点的度:
树的度:
叶子结点:
分支结点:
数据元素+若干指向子树的分支
分支的个数
树中所有结点的度的最大值
度为零的结点
度大于零的结点
D
H
I
J
M
(从根到结点的)路径:
孩子结点、双亲结点、
兄弟结点、堂兄弟
祖先结点、子孙结点
结点的层次:
树的深度:
由从根到该结点所经分支和结点构成
A
B
C
D
E
F
G
H
I
J
M
K
L
假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1
树中叶子结点所在的最大层次