数据结构-树.ppt

文档介绍：第五章树
本章内容:
* 树的定义和基本操作;
* 二叉树的定义及遍历、存储结构;
* 树的应用;
重点:
* 树的定义
* 二叉树的定义及遍历序列
内容
§ 树的定义和基本术语
§ 二叉树的定义及存储结构
§ 二叉树的遍历
§ 树的存储
§ 树的应用
§ 树的定义和基本术语
一、树的定义
树是由n个结点构成的有限集合。
当n=0时,称为空树。
在一棵非空树中(n>0)中,有且仅有一个特定的结点,称根的结点;其余结点可分为m个(m≥0)互不相交的集合T1,T2……Tm,其中,每一个集合本身又是一棵树,且称为根的子树。
※特点:
树中至少有一个结点—根,它没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点;
树中各子树是互不相交的集合,树中所有结点可以有零个或多个后继结点。
有限集合T1,T2……Tm应该“互不相交”,即任意两个集合不能有相重的结点。
※树的各个结点有不同层次关系,这种关系通常用图形表示,但与自然界的树木相反****惯上将整棵树的根画在最上层,
A
B
C
D
E
F
G
H
I
J
K
L
M
有子树的树
根
子树
A
只有根结点的树

二、树的相关术语
结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支
结点的度(degree)——结点拥有的子树个数
叶子(leaf)——度为0的结点
孩子(child)——结点子树的根称为该结点的孩子
双亲(parents)——孩子结点的上层结点叫该结点的~
兄弟(sibling)——同一双亲的孩子
树的度——一棵树中最大的结点度数
※结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……
※深度(depth)——树中结点的最大层次数
※森林(forest)——m(m0)棵互不相交的树的集合
※有序树- 树中结点的各子树从左到右是有次序的,否则为无序树。
例:
,回答问题:
A
B
C
D
E
F
G
H
I
J
K
L
M
结点A的度:3
结点B的度:2
结点M的度:0
树的度:3
结点A的孩子:B,C,D
结点B的孩子:E,F
结点A的层次:1
结点M的层次:4
叶子:K,L,F,G,M,I,J
结点I的双亲:D
结点L的双亲:E
结点B,C,D为兄弟
结点K,L为兄弟
结点F,G为堂兄弟
结点A是结点F,G的祖先
树的深度:4

三、树的表示方法
1、直观表示法:

2、文氏图法:
h
b
a
c
g
d
e
f
i
j
i
j
d
f
g
h
a
b
e
3、嵌套括号法

4、凹入表示法
a ( b ( d, e ( i, j ), c ( g, h ) ) )
a
b
d
e
i
j
f
c
g
h