中国地名汉语拼音字母拼写规则(汉语地名部分)(1984-12-25).doc

第五章树与二叉树
数据结构电子教案
殷人昆
1
第五章树与二叉树
树和森林的概念
二叉树
二叉树遍历
二叉树的计数
线索化二叉树
树与森林
堆
Huffman树
2
树和森林的概念
两种树:自由树与有根树。
自由树:
一棵自由树 Tf 可定义为一个二元组
Tf = (V, E)
其中V = {v1, ..., vn} 是由 n (n>0) 个元素组成的有限非空集合,称为顶点集合。E = {(vi, vj) | vi, vj V, 1≤i, j≤n} 是n-1个序对的集合,称为边集合,E 中的元素(vi, vj)称为边或分支。
3
自由树
有根树:
一棵有根树 T,简称为树,它是n (n≥0) 个结点的有限集合。当n = 0时,T 称为空树;否则,T 是非空树,记作
4
r 是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱;
根以外的其他结点划分为 m (m  0) 个互不相交的有限集合T1, T2, …, Tm,每个集合又是一棵树,并且称之为根的子树。
每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。
5
兄弟:同一结点的子女互称为兄弟。
度:结点的子女个数即为该结点的度;树中各个结点的度的最大值称为树的度。
分支结点:度不为0的结点即为分支结点,亦称为非终端结点。
叶结点:度为0的结点即为叶结点,亦称为终端结点。
祖先:某结点到根结点的路径上的各个结点都是该结点的祖先。
子孙:某结点的所有下属结点,都是该结点的子孙。
7
结点的层次:规定根结点在第一层,其子女结点的层次等于它的层次加一。以下类推。
深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。
1层
2层
4层
3层
depth
= 4
D
A
C
B
I
J
H
G
F
E
M
L
K
height
= 4
8
高度:规定叶结点的高度为1,其双亲结点的高度等于它的高度加一。
树的高度:等于根结点的高度,即根结点所有子女高度的最大值加一。
有序树:树中结点的各棵子树 T0, T1, …是有次序的,即为有序树。
无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。
森林:森林是m(m≥0)棵树的集合。
9
树的抽象数据类型
template <class T>
class Tree {
//对象: 树是由n (≥0) 个结点组成的有限集合。在
//类界面中的 position 是树中结点的地址。在顺序
//存储方式下是下标型, 在链表存储方式下是指针
//型。T 是树结点中存放数据的类型, 要求所有结
//点的数据类型都是一致的。
public:
Tree ();
~Tree ();
10