数据结构与算法—赵玉兰 第4章 树与二叉树.ppt

树的定义和相关术语
二叉树
树和森林
森林与二叉树的关系
Huffman树与编码
1
树的定义和相关术语
二叉树
树和森林
森林与二叉树的关系
Huffman树与编码
2
内蒙古大学
理工学院
计算机学院
生命科学学院
外国语学院
人文学院
数学系
物理系
电子系
计算机系
计算中心
网络中心
汉语系
历史系
哲学系
生物系
环境系
动物中心
生物工程中心
资源所
英语系
日语系
行政机构
树形结构是一种非线性结构,应用十分广泛。
如:行政机构、目录、家谱等。
3
磁盘目录
4
红楼梦家谱
5
树和森林的概念
树的定义
树是由 n (n ≥ 0) 个结点组成的有限集合。如果 n = 0,称为空树;如果 n > 0,则
有一个特定的称之为根(root)的结点,它只有直接后继,但没有直接前驱;
除根以外的其他结点被划分到 m (m ≥ 0) 个互不相交的子集T1, T2, …, Tm中,每个子集又都构成一棵树,称之为根的子树(sub tree)。
6
树的特点
每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。
树是一种典型的“层次结构”,体现出“一对多”的关系。
A
C
G
B
D
E
F
K
L
H
M
I
J
7
: Tree=(D, R)
D={Book, C1, C2, C3, , , , , , , }
R={ <Book, C1>, <Book, C2>, <Book, C3>, <C1, >,
<C1, >, <C2, >, <C2, >, <C2, >,
<, >, <, > }
Book
C1
C2
C3







Chapter
Section
Sub-Section
8
基本术语:主要来源于家谱和自然界中的树。
双亲、子女(parent, child):
若<a,b>R,则称a是b的双亲,b是a 的子女(孩子);
结点度(degree):
结点所拥有的子女数;
叶子(leaf):
度为0的结点;
分枝结点(branch node):
度大于0的结点;
树的度:树中最大的结点的度;
A
B
C
D
E
F
G
H
I
J
M
K
L
9
结点所在的层次(level):根在第1层,其它任一结点所在的层是其双亲的层数加1。
深度或高(depth):树中结点的最大层数。
兄弟(sibling):同一双亲的结点间互称兄弟。
堂兄弟(cousin):同层的非兄弟结点互称堂兄弟。
4
2
3
A
B
C
D
E
F
G
H
I
J
M
K
L
1
10