数据结构第六章.ppt

第6章树和二叉树
学****目的与要求:
1. 熟练掌握二叉树的结构特性,了解相应的证明方法;
2. 熟悉二叉树的各种存储结构的特点及适用范围;
3. 熟练掌握二叉树各种遍历策略的递归和非递归算法,而且能灵活运用遍历算法实现二叉树的其它操作;
4. 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
5. 熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。
6. 了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。
基本内容
一、树的定义和基本术语
二、二叉树的定义及性质
三、二叉树的存储结构
四、遍历二叉树
五、线索二叉树
六、树和森林
七、哈夫曼树及其应用
八、本章小结
一、树的定义和基本术语
(1)树的定义:
树是一种常用的非线性数据结构。它是n(n>=0)个结点的有限集。 n=0时,称为空树。在任意一棵非空树中:1)有且仅有一个特定的称为根(Root)的结点;2)当n>1时,其余结点分为m(m>0)个互不相交的有限集T1, T2, …, Tm,其中每一个集合本身又是一棵树,并且称为根的子树。
(2)树的特点:
有且只有一个称作根的结点;
除根结点以外,其余结点有且只有一个双亲结点。
(3)树的示例:
A
B
C
D
E
F
G
H
I
J
K
L
M
有子树的树
A
只有根结点的树
子树
(4)树的基本术语:
A
B
C
D
E
F
G
H
I
J
K
L
M
结点(node) ——表示树中的元素,包括数据项及若干指向其子树的分支。
结点的度(degree) ——结点拥有的子树数。
叶子(leaf) ——度为0的结点,又称终端结点。
孩子(child) ——结点子树的根称为该结点的孩子,该结点称为其孩子结点的双亲(parents)
兄弟(sibling) ——同一双亲的孩子。
树的度——一棵树中各结点的度的最大值。
结点的层次(level) ——从根结点算起,根为第一层,它的孩子为第二层…
深度(depth) ——树中结点的最大层次数。
森林(forest) ——m(m≥0)棵互不相交的树的集合。
另:祖先、子孙、堂兄弟、非终端结点、内部结点、
无序树、有序树等
(5)树的基本运算:
(1) InitTree(&T): 构造一棵空树
(2) TreeDepth(T): 求树的深度
(3) Root(T): 求树根
(4) Parent(T, cur_e): 求树T中结点cur_e的双亲
(5) LeftChild(T, cur_e): 若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回“空”。
(6) RightSibling(T, cur_e): 若cur_e有右兄弟,则返回它的右兄弟,否则函数值为“空”。
(7) InsertChild(&T, &p, i, c ): 插入c为T中p指结点的第i棵子树。
(8) DeleteChild(&T, &p, i): 删除T中p所指结点的第i棵子树。
(9) TraverseTree(T, visit()): 按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败,则操作失败。
……
(5)树的表示法:
返回
广义表表示法
(
a
(
b
(
d
,
e
(
i
,
j
)
,
f
)
,
c
(
g
,
h
)))
二、二叉树的定义和性质
二叉树(binary tree): 度不超过2的有序树,是另一种树型结构。
特点:◆每个结点至多只有两棵子树;
◆二叉树的子树有左右之分,其次序不能任意颠倒。
二叉树的五种基本形态:
(a)空二叉树
A
(b)仅有根结点的二叉树
(c)右子树为空的二叉树
A
(d)左、右子树均非空的二叉树
A
(e)左子树为空的二叉树
A
(1)二叉树的定义:
(2)二叉树的基本运算:
(1) InitBiTree(&T): 构造一棵空二叉树;
(2) BiTreeDepth(T): 求二叉树的深度;
(3) BiTreeEmpty(T): 若T为空二叉树,则返回TRUE,否则FALSE;
(4) Parent(T, e): 若e是T的非根结点,则返回它的的双亲,否则返回“空”;
(5) LeftChild(T, e): 返回e的左孩子,若e无左孩子,则返回“空”;
(6) RightChild(T, cur_e): 返回e的右孩子,若e无右孩子,则返回“空”;
(7) InsertChild(&T, &p, LR, c ): 插入c为T中p指结点的由LR的值确定的左(右)子树;
(8) DeleteChild(&T