第6章形结构5

1、2021-11-12第六章 树和二叉树1 假设有假设有n个权值个权值w1, w2, , wn，构造一，构造一棵有棵有 n个叶子结点的二叉树，每个叶子结点带个叶子结点的二叉树，每个叶子结点带权为权为wi ，则其中带权路径长度，则其中带权路径长度wpl最小的二最小的二叉树称做叉树称做最优二叉树最优二叉树或或哈夫曼树。哈夫曼树。 权值越大的结点离根越近的二叉树才是最优二权值越大的结点离根越近的二叉树才是最优二叉树。叉树。 哈夫曼树不唯一。哈夫曼树不唯一。 哈夫曼树是一种最优树，可用于电位的编码和译码。2021-11-12第六章 树和二叉树2 abcd7524(a)a7b5cd6(b)a7bcd11(

2、 c )abcd18( d )2021-11-12第六章 树和二叉树3 (1)根据给定的根据给定的n个权值个权值w1, w2, , wn，构造构造n棵二叉树的集合棵二叉树的集合f = t1, t2, , tn，其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为wi的根的根结点结点,其左、右子树为空树其左、右子树为空树; (2)在在f中选取其根结点的权值为最小的两棵二中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权

3、值之和右子树根结点的权值之和; (3)从从f中删去这两棵树，同时加入刚生成的新中删去这两棵树，同时加入刚生成的新树树; 重复重复(2)和和(3)两步，直至两步，直至f中只含一棵树中只含一棵树为止。为止。2021-11-12第六章 树和二叉树4 规定哈夫曼树中的左分支为规定哈夫曼树中的左分支为0,右分支为右分支为1,则从根结点到每个叶结点所经过的分支对则从根结点到每个叶结点所经过的分支对应的应的0和和1组成的序列便为该结点对应字符组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。的编码。这样的编码称为哈夫曼编码。2021-11-12第六章 树和二叉树5对应的哈夫曼编码如下：对应的哈夫

4、曼编码如下：1：000 3：001 5：01 7：12021-11-12第六章 树和二叉树6哈夫曼编码举例 例：已知某系统在通信联络中可能出现例：已知某系统在通信联络中可能出现8种字符，种字符，其概率为其概率为0.05, 0.29, 0.07, 0.08, 0.l4, 0.23, 0.03, 0.11, 试设计哈夫曼编码。试设计哈夫曼编码。 解：设权解：设权w=(5,29,7,8,14,23,3,11), 根据根据哈夫曼算法可构造哈夫曼树。哈夫曼算法可构造哈夫曼树。531123781429000000011111112021-11-12第六章 树和二叉树76.6 6.6 二叉树的构造二叉树的构

5、造 同一棵二叉树具有惟一先序序列、中序序列和同一棵二叉树具有惟一先序序列、中序序列和后序序列后序序列,但不同的二叉树可能具有相同的先序序列、但不同的二叉树可能具有相同的先序序列、中序序列和后序序列。中序序列和后序序列。 2021-11-12第六章 树和二叉树8 定理定理6.1：任何：任何n(n0)个不同结点的二又树个不同结点的二又树,都可由都可由它的中序序列和先序序列惟一地确定。它的中序序列和先序序列惟一地确定。2021-11-12第六章 树和二叉树9 a0 a1 ak ak+1 an-1 根结点 左子树先序序列,有k个结点 右子树先序序列,有n-k-1个结点 b0 b1 bk-1 bk bk

6、+1 bn-1 根结点 左子树中序序列,有k个结点 通过 a0在中序序列中找到 bk 右 子 树 中 序序列,有 n-k-1个结点 先序序列: 中序序列: 2021-11-12第六章 树和二叉树10 例如例如,已知先序序列为已知先序序列为abdgcef,中序序列为中序序列为dgbaecf,则构造二叉树的过程如下所示。则构造二叉树的过程如下所示。 根结点：根结点：a左先序左先序:bdg 左中序左中序:dgb右先序右先序:cef 右中序右中序:ecf根结点：根结点：b左先序左先序:dg 左中序左中序:dg右先序右先序:空空 右中序右中序:空空根结点：根结点：d左先序左先序:空空 左中序左中序:空空

7、右先序右先序:g 右中序右中序:g根结点：根结点：g左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空根结点：根结点：c左先序左先序:e 左中序左中序:e右先序右先序:f 右中序右中序:f根结点：根结点：e左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空根结点：根结点：f左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空2021-11-12第六章 树和二叉树11 定理定理6.2：任何任何n(n0)个不同结点的二又树个不同结点的二又树,都可都可由它的中序序列和后序序列惟一地确定。由它的中序序列和后序序列惟一地确定。

8、a0 a1 ak-1 ak an-2 an-1 根结点 左 子 树 后序序列,有k个结点 右子树后序序列,有 n-k-1 个结点 b0 b1 bk-1 bk bk+1 bn-1 根结点 左子树中序序列,有k个结点 通过 an-1在中序序列 右子树中序序列,有 n-k-1个结点 后序序列: 中序序列: 中找到 bk 2021-11-12第六章 树和二叉树12 例如例如,已知中序序列为已知中序序列为dgbaecf,后序序列为后序序列为gdbefca。对应的构造二叉树的过程如下所示。对应的构造二叉树的过程如下所示。 根结点：根结点：a左中序左中序:dgb 左根左根:b右中序右中序:ecf 右根右根:c根结点：根结点：b左中序左中序:dg 左根左根:d右中序右中序:空空 右根右根:空空根结点：根结点：d左中序左中序:空空 左根左根:空空右中序右中序:g 右根右根:g根结点：根结点：g左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空根结点：根结点：c左中序左中序:e 左根左根:e右中序右中序:f 右根右根:f根结点：根结点：e左中序左中序:空空 左根左根:空空