第6讲树与二叉树36634

Huffman常译为赫夫曼、霍夫曼、哈夫曼等
9
树的带权路径长度 如何计算？
经典之例：
n
WPL =k=1 wklk
树中所有叶子结 点的带权路径长 度之和
75 2 4 a bc d
(a)
WPL= 36
2 c 4 d 75 ab (b)
WPL= 46
7 a
5 b
24 cd
(c)
WPL= 35
Huffman树是WPL 最小的
11
2. 构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F =
{ T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个
带权为 wi 的根结点，其左右子树均空。 (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新
5
5
2
6
4
10
1
4
3
10 7
9
8
（a）
2 13
67
（b）
8 9
想一想：对它中序遍历之后是什么效果？
4
什么是判定树？
举例： 12个球如何用天平只称3次便分出轻重？
分析： 12个球中必有一个非轻即重，即共有24种“次品”的可能性。 每次天平称重的结果有3种，连称3次应该得到的结果有33=27 种。 说明仅用3次就能找出次品的可能性是存在的。
12
具体操作步骤：
step1：对权值进行合并、删除与替换
——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权
a. 初始
c. 合并{5} {6}
d. 合并{7} {11}

§6.2 二叉树
❖二叉树的定义
或者是空树，或者是由一个根结点加上两棵 分别称为左子树和右子树的、互不相交的二叉树 组成。
二叉树的结点的子树要区分左子树和右子树， 即使在结点只有一棵子树的情况下也要明确指出 该子树是左子树还是右子树。
§6.2 二叉树
❖二叉树的定义
逻辑结构： 一对二（1：2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点） ② 左子树和右子树次序不能颠倒（有序树）。 基本形态：
§6.1 树的基本概念
❖树的基本术语
结点 ——即树的数据元素 结点的度 ——结点挂接的子树数
（有几个直接后继就是几度， 亦称“次数”） 结点的层次 ——从根到该结点的层数（根结点算第一层） 终端结点 ——即度为0的结点，即叶子 分支结点 ——即度不为0的结点（也称为内部结点） 树的度 ——所有结点度中的最大值（Max{各结点的度}） 树的深度 ——指所有结点中最大的层数（Max{各结点的层次}） (或高度)
二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操 作必须建立在对树结点能够“遍历”的基础上！ （遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。
§6.2 二叉树
❖二叉树的性质
讨论1：第i层的结点数至多是多少？ 2i-1个
1
2
3
（二进制性质）
4
5
6
7
8 9 10 11 12 13 14 15
特点：每层都“充满”了结点
§6.2 二叉树
❖两种特殊形式的二叉树
完全二叉树：树中所含的n个结点和满二叉树中编号 为1至n的结点一一对应
(例如删除A后的子树个数) 有序树 ——结点各子树从左至右有序，不能互换（左为第一） 无序树 ——结点各子树可互换位置。

B所代表的这些分支都是由度为1和度为 2的结点发出的，一个度为1的结点发出1 个分支，一个度为2的结点发出2个分支， 所以有： B＝n1＋2n2 综上所述，可以得到： n0＝n2＋1
性质4 具有n个结点的完全二叉树的深度k为 [log2n]+1。 证明 根据完全二叉树的定义和性质2可知，当 一棵完全二叉树的深度为k、结点个数为n时，有 2k－1－1<n≤2k-1 即 2k－1≤n<2k 对该不等式取对数，有 k－1≤log2n< k 即 log2n< k≤log2n+1 由于k是整数，所以有k＝[log2n]+1。
性质2 一棵深度为k的二叉树中，最多具 有2k－1个结点。
证明 设第i层的结点数为mi（1≤i≤k），深 度为k的二叉树的结点数为N，由性质1 知第i层的结点数mi最多为2i-1，则有： N＝ mi≤ 2i-1 ＝2k-1
性质3 对于一棵非空的二叉树，设叶子结 点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。 证明 设n为二叉树的结点总数，n1为二叉 树中度为1的结点数，则有： n＝n0＋n1＋n2 在二叉树中，除根结点外，其余结点都 有双亲，所以这些结点都有唯一的一个分支 来指向。 设B为二叉树中的分支数，那么有： B＝n－1
性质5 对于具有n个结点的完全二叉树，如果按 照从上往下和从左至右的顺序对二叉树中的所有 结点从1开始顺序编号，则对于任意的序号为i的 结点，有： (1) 如果i>1，则序号为i的结点的双亲结点的序号 为i/2；如果i＝1，则序号为i的结点是根结点， 无双亲结点。 (2) 如果2i≤n，则序号为i的结点的左孩子结点 的序号为2i；如果2i>n，则序号为i的结点无左孩子。 (3) 如果2i＋1≤n，则序号为i的结点的右孩子结点 的序号为2i＋1；如果2i＋1>n，则序号为i的结点无 右孩子。

^d ^ ^ e ^ 三叉链表
3）二叉链表是二叉树最常用的存储结构。还有其它链接方 法，采用何种方法，主要取决于所要实施的各种运算频度。
例:若经常要在二叉树中寻找某结点的双亲时，可在每个结 点上再加一个指向其双亲的指针域parent，称为三叉链表。
lchild data parent rchild
2021/8/16
2021/8/16
9
6.2 二 叉 树
6.2.1 二叉树的概念
一、二叉树的定义： 二叉树(Binary Tree)是n(n>=0)个结点的有限集，它或者是 空集(n=0)或者由一个根结点和两棵互不相交的，分别称 为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定 义。
A
集合3
集合1
BCD
EF
G
集合2
2021/8/16
3
2、树的表示方法 1）树形图法
A
BCD
EF
G
2）嵌套集合法
3）广义表形式 ( A(B, C(E,F), D(G) )
4）凹入表示法
2021/8/16
A B
D
CG
EF
A B C E DF G
4
3、 树结构的基本术语
1）结点的度(Degree)：为该结点的子树的个数。 2）树的度：为该树中结点的最大度数。
7）路径(Path)：若树中存在一个结点序列k1,k2,…,kj,使得ki是 ki+1的双亲(1<=i<j)，则称该结点序列是从ki到kj一条路径 (Path)
路径长度：路径的长度为j-1,其为该路径所经过的边的数 目。
A
BCD
EF
G