教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net.

Presentation on theme: "教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net."— Presentation transcript:

1 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net
计算机软件技术基础 教 师：曾晓东 电 话： E_mail:

2 非线性结构 逻辑特征：一个结点可能有多个直接前驱和直接后继。 类型：树型结构、图形结构。 计算机软件技术基础 第四章 树形结构

3 第四章 树形结构 树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。
树型结构在客观世界中广泛应用，例如家族关系中的家谱、各种社会组织机构、一本书中的章节划分、操作系统中的多级目录结构、高级语言中源程序的语法结构等。 本章主要讨论树及二叉树的定义及其存储结构，重点讨论二叉树的特性以及应用。 计算机软件技术基础 第四章 树形结构

4 第四章 树形结构 一、树的基本概念及存储结构 二、二叉树 三、二叉树的操作 四、树、森林与二叉树的关系 五、二叉排序树
六、哈夫曼树与哈夫曼算法 计算机软件技术基础 第四章 树形结构

5 一、树的基本概念及存储结构 A B D K E F L M J I H G C root 1、树的定义和术语  树的定义
1）定义：树是由n(n≥0)个结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m≥0)个各互不相交的有限集合T1、T2、…、Tm，其中每一个集合Ti本身又是一棵树，称为根结点root的子树。当n=0时称为空树。 2）树是一种具有递归性质的结构。 3）树的根结点没有直接前驱，其余结点有且仅有一个直接前驱，所有结点可以有0个或多个直接后继。 计算机软件技术基础 第四章 树形结构

6 一、树的基本概念及存储结构 A B D K E F L M J I H G C root 1 2 3 4  常用术语
1）结点：表示树中的元素。如A、B、K等 2）度：结点拥有的子树数。如A的度为3，C的度为1。一棵树中最大的结点度数为这棵树的度。上图中树的度为3。 3）叶子：度为0的结点，又称终端结点，如K、L、G等。 4）孩子：结点的子树的根，如B、C、D均是A的孩子。 5）双亲：相应地，该结点称为孩子的双亲，如A是B、C、D的双亲 计算机软件技术基础 第四章 树形结构

7 一、树的基本概念及存储结构 A B D K E F L M J I H G C root 1 2 3 4
6）子孙：以某结点为根的子树中的任一结点称为该结点的子孙。 7）祖先：从根到该结点所经分支上的所有结点。 8）兄弟：同一双亲的孩子。 9）结点的层次：从根结点开始算起，根为第一层，根的直接后继结点为第二层，以此类推。 10）高度（深度）：树中结点的最大层次数。 计算机软件技术基础 第四章 树形结构

8 一、树的基本概念及存储结构 11）森林：是m(m≥0)棵互不相交的树的集合
12）有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树；反之称为无序树。 A B D K E F L M J I H G C T1 T2 T3 root 1 2 3 4 计算机软件技术基础 第四章 树形结构

9 一、树的基本概念及存储结构 · A · · · B · ^ ^ E ^ ^ ^ F ^ ^ ^ C ^ · ^ D ^ ^ ^ G ^ ^
2、树的存储结构 1）树是多分支非线性表，因此需要采用多重链表结构，即每个结点设有多个指针域，其中每一个指针指向一棵子树的根结点。如图： 2）结点异构型和结点同构型。 结点异构型：不定长度结点的多重链表 省空间，但运算复杂 结点同构型：采用定长度结点的多重链表，均按树的度数设指针域 运算方便，但有许多域为空，浪费空间 计算机软件技术基础 第四章 树形结构

10 一、树的基本概念及存储结构 · A · · · B · ^ ^ E ^ ^ ^ F ^ ^ ^ C ^ · ^ D ^ ^ ^ G ^ ^
3）空链域问题：假设有一棵具有n个结点、度为k的树，采用同构型存储结构，那么有多少个空链域？ 总链域=n*k； 考虑每个结点只有一个双亲，因此指向该结点的指针只有一个，但根结点无双亲，因此无指针指向它 非空链域=n-1； 所以，空链域=n(k-1)+1。 解决方法：转化为二叉树 计算机软件技术基础 第四章 树形结构

11 一、树的基本概念及存储结构 序号 双亲数组表示法
一棵有n个结点的树，用一维数组tree[n]来表示，在tree[1……n]中每个tree[i]（1≤i≤n）是一个记录，它包含两个域：data和Parent域，其中，tree[i].data表示树的一个结点，tree[i].Parent存放该结点的双亲在tree[1……n]中的序号(下标)，如果tree[i].data表示tree的root，则tree[i].Parent=0。如： A G F E I H D C B 9 8 7 6 5 4 3 2 1 I H G F E D C B A Parent Data 序号 计算机软件技术基础 第四章 树形结构

12 二、二叉树 1、二叉树的定义 1）二叉树是n(n≥0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。这也是一个递归定义。 2）二叉树的五种不同形态 计算机软件技术基础 第四章 树形结构

13 二、二叉树 2、二叉树的性质 1）二叉树的第i层上至多有2i-1(i≥1)个结点可用归纳法证明。
2）深度为h的二叉树中至多含有2h - 1个结点。由性质1求和即可证明。 3）在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+1。 计算机软件技术基础 第四章 树形结构

14 二、二叉树 证明：设n1为度为1的结点，则结点总数为 n=n0+n1+n2； 又分支总数为：b=n1+2n2； 而n=b+1；
计算机软件技术基础 第四章 树形结构

15 二、二叉树 1 2 6 5 7 4 3 15 14 13 12 11 10 9 8 定义1 满二叉树(Full Binary Tree)
一棵深度为k 且有2k-1个结点的二叉树。 定义2 完全二叉树(Complete Binary Tree) 如果一棵有n个结点的二叉树按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1～n编号完全一致，则称该二叉树为完全二叉树。 1 2 6 5 7 4 3 12 11 10 9 8 1 2 6 5 7 4 3 12 11 10 9 8 计算机软件技术基础 第四章 树形结构

16 二、二叉树 4) 具有n个结点的完全二叉树的深度为[log2 n]+1 证明：设完全二叉树的深度为h，则有
2h-1-1 < n  2h-1 2h-1  n < 2h 取对数 h–1  log2(n) < h 计算机软件技术基础 第四章 树形结构

17 二、二叉树 1 2 6 5 7 4 3 12 11 10 9 8 5) 对于—棵有n个结点的完全二叉树，对编号为i的结点(1≤i≤n)，有：
如果 i > 1，则编号为i的结点的双亲为结点[ i/2 ]。 如果 2i > n，则编号为i的结点没有左子树。 如果 2i ≤ n，则编号为i的结点的左子树是2i 。 如果2i+1 > n，则编号为i的结点没有右子树。 如果2i+1 ≤n，则编号为i的结点的右子树是2i十1。 计算机软件技术基础 第四章 树形结构

18 二、二叉树 3、二叉树的顺序存储结构 完全二叉树的数组表示 一般二叉树的数组表示 计算机软件技术基础 第四章 树形结构

19 二、二叉树 由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。 例:深度为k的单支二叉树,
只有k个结点,却需2k－1个单元 计算机软件技术基础 第四章 树形结构

20 二、二叉树 B A D F E C A ^ ^ F ^ ^ E ^ ^ C ^  3、二叉树的链式存储结构
二叉树采用二叉链表进行存储。每个结点由数据域(data)、左指针域(lchild)、右指针域(rchild)组成。 类型定义 struct bitree { elemtype data ; bitree *lchild; bitree *rchild; } 缺点: 查找双亲结点不便 计算机软件技术基础 第四章 树形结构

21 二、二叉树 三叉链表 计算机软件技术基础 第四章 树形结构

22 三、二叉树的操作 1、遍历是指循某条搜索路线依次访问某数据结构中的全部结点，而且每个结点只被访问一次。
1）由于一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，所以遍历二叉树就是依次遍历这三部分。 2）若我们以D、L、R分别表示访问根结点、遍历左子树、遍历右子树，则可以有以下6种形式： DLR,DRL,LDR,LRD,RDL,RLD。 3）若规定先左后右，则有以下3种形式： DLR：先序遍历; LDR：中序遍历; LRD：后序遍历 说明：其中的序是针对根结点来说的。 计算机软件技术基础 第四章 树形结构

23 三、二叉树的操作 A G F D C E B 4） 过程描述（以先序遍历为例）
若二叉树为空，则为空操作，否则先访问根结点，然后先序遍历左子树，再先序遍历右子树。这是一个递归定义。 5）举例： 如上图所示二叉树中，遍历的结果为： 先序：A B C D E F G 中序：C B D A E G F 后序：C D B G F E A 计算机软件技术基础 第四章 树形结构

24 三、二叉树的操作 例：已知结点的先序序列和中序序列，求整棵二叉树。 先序序列：A B C D E F G
中序序列：C B E D A F G A B C F D E G A C B E D F G A B C D E F G 计算机软件技术基础 第四章 树形结构

25 三、二叉树的操作 2、函数实现(以中序遍历为例) void inorder(bitree * BT){
表达式语法树 三、二叉树的操作 2、函数实现(以中序遍历为例) void inorder(bitree * BT){ if(BT == NULL ) return ; if(BT->lchild != NULL) inorder(BT->lchild); visite(BT); if(BT->rchild != NULL) inorder(BT->rchild); } 在遍历二叉树的算法中，基本操作是访问结点，对含有n个结点的二叉树来说，其时间复杂度均为O(n)，所需辅助空间是遍历过程中栈的最大容量，也就是树的深度，最坏情况下为n。 遍历结果 a + b * c - d - e / f 计算机软件技术基础 第四章 树形结构

26 三、二叉树的操作 3、应用 1) 二叉树的复制(采用先序遍历)
bitree * copyTree(bitree *source) { if (!source) return(null);//空树 bitree *dest = new bitree; dest->data = source->data; dest->lchild = copyTree(source->lchild); dest->rchild = copyTree(source->rchild); return dest; } 计算机软件技术基础 第四章 树形结构

27 三、二叉树的操作 2）求树的高度（后序遍历） int treeHigh(bitree *BT)
{ if (!BT) return(0);//空树 if (!BT->lchild&&!BT->rchild)//只有根 return(1); //其它情况，树的高度为左右子树高度中最大者加一 int lhigh = treeHigh(BT->lchild); int rhigh = treeHigh(BT->rchild); return (lhigh>rhigh)?lhigh+1:rhigh+1; } 计算机软件技术基础 第四章 树形结构

28 三、二叉树的操作 3) 求二叉树中的叶子数(后序遍历）
int CountLeaf(bitree *BT) { if (!BT) return(0);//空树 if (!BT->lchild&&!BT->rchild)//只有根 return(1); else//其它情况，左右子树叶子之和 return(CountLeaf(BT->lchild) +CountLeaf(BT->rchild)); } 计算机软件技术基础 第四章 树形结构

29 四、树、森林与二叉树的关系 1、树的多链表示 我们讲过，树在计算机内部有两种多重链表表示方法：
● 采用不定长度结点的多重链表来表示树，这种表示方法虽然可以节省存储空间，但给存储分配和各种运算带来很大的麻烦 ● 采用固定长度结点的多重链表来表示树，这样，存储分配和各种运算比较方便，只不过存储空间浪费很大。 计算机软件技术基础 第四章 树形结构

30 四、树、森林与二叉树的关系 例如：设树T为k叉树(即树的度为k)，并有n个结点，当用固定长度结点的多重链表进行表示时，每个结点都有k个指针域，则n个结点应该有n*k个指针域。但是，树T只有n个结点，除去根结点，其他每个结点都只有一个指向它的指针，因为每个结点只能有一个直接前趋。因此，n个结点只需要n一1个指针，这就是说，n*k个指针域中只有n一1个指针域是非空的，而其余的指针域都是空的。 树的度数越大，则空指针域就越多，存储空间的浪费就越大。 计算机软件技术基础 第四章 树形结构

31 四、树、森林与二叉树的关系 E A C B D I H G F E A C B D I H G F E A C B D I H G F
2、树的二叉树表示 1）为了让一般树也能像二叉树一样用二叉链表表示，必须找出树与二叉树之间的关系，这样当给定一棵树时，可以找到唯一的一棵二叉树与之对应，而且这种关系的逆变换也是存在的。 2）一般树中的结点次序没有要求，为了得到对应的二叉树，则需对树中每个孩子结点进行自左至右的排序。 3）将一般树转换为二叉树的方法为：（如图） ① 在兄弟结点之间加一连线； ② 对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系； ③ 以树根为轴心，将整棵树顺时针旋转45°。 计算机软件技术基础 第四章 树形结构

32 四、树、森林与二叉树的关系 4）由树转换而得的二叉树的特点 二叉树的根结点没有右子树。
每个结点的右子树都是原来树中该结点的兄弟，而该结点的左子树都是原来树中该结点的子树。 二叉树中任一结点的左孩子是此结点在树中的第一个孩子 二叉树中任一结点的右孩子是此结点在树中的下一个兄弟 因此，树的这种表示法又称树的孩子-兄弟表示法 计算机软件技术基础 第四章 树形结构

33 四、树、森林与二叉树的关系 A B C D E F G 5）类型定义 struct treenode {
struct elemtype data ; struct treenode *firstChild; struct treenode *nextSibling; } data firstChild nextSibling G D E A B C F A B C D E F G 计算机软件技术基础 第四章 树形结构

34 四、树、森林与二叉树的关系 K J I D E H G C F B A K J I H Ⅲ A B D E C Ⅰ G F Ⅱ A B C
3、森林的二叉树表示 先把森林中的每一棵树依次转换成相应的二叉树; 然后,将第2棵二叉树作为第1棵二叉树的根结点的右子树连接起来，将第3棵二叉树作为第2棵二叉树的根结点的右子树连接起来,……直至把所有的二叉树连接成为一棵二叉树。 第一棵树的根结点就是最后生成的二叉树的根结点。 转换中的二叉树 转换后的二叉树 计算机软件技术基础 第四章 树形结构

35 五、二叉排序树 12 15 14 11 9 13 10 1. 定义 二叉排序树或是一棵空树，或是满足以下特征的非空二叉树：
1）每个元素有一个关键值； 2）根结点左子树的关键值均小于根结点的关键值 3）根结点右子树的关键值均大于根结点的关键值 4）根结点的左右子树也都是符合本定义的二叉排序树 特点：对二叉排序树进行中序遍历，可得到有序序列。 计算机软件技术基础 第四章 树形结构

36 五、二叉排序树 45 78 12 3 37 53 100 24 90 61 二叉排序树 2. 二叉排序树的查找 与折半查找类似
从根结点出发，结点的值与key进行比较： （1）相等时查找成功； （2）key较大时，沿右子树继续查找（无右子树表明查找失败）； （3）key较小时，沿左子树继续查找（无左子树表明查找失败）。 计算机软件技术基础 第四章 树形结构

37 2. 二叉排序树的查找 bitree * search(bitree *BT, elemtype a){
if(!BT) return(null); // 查找不成功 if(BT->data==a) return BT; if(BT->data>a) // 查找左子树 return search(BT->lchild,a); if(BT->data<a) // 查找右子树 return search(BT->rchild,a); } 计算机软件技术基础 第四章 树形结构

38 五、二叉排序树 3. 二叉排序树的插入算法 根据二叉排序树的定义，插入操作在查找不成功时才进行 若二叉排序树为空，则新插入结点为根结点
否则，新插入结点为新的叶子结点，其位置由查找决定 计算机软件技术基础 第四章 树形结构

39 3. 二叉排序树的插入算法 bitree * insertTree(bitree *BT, elemtype a){
if(!BT) { // 生成新的结点 BT = new bitree; BT->data = a; BT->lchild = null; BT->rchild = null; }else if(BT->data>a) // 结点放入左子树 BT->lchild = insertTree(BT->lchild,a); else if(BT->data<a) // 结点放入右子树 BT->rchild = insertTree(BT->rchild,a); return BT; } 计算机软件技术基础 第四章 树形结构

40 五、二叉排序树 45 45 45 45 45 4. 二叉排序树的生成 二叉排序树的生成(连续进行插入操作)
例如:对{45,24,53,45,12,24,90} 关键字序列的二叉排序树生成过程如下: 45 24 45 24 53 45 45 24 12 53 45 24 12 53 90 计算机软件技术基础 第四章 树形结构

41 五、二叉排序树 5. 删除二叉排序树上的结点 删除结点需保持二叉排序树的特性及次序
设被删除的结点为p,其父结点为f,并不失一般性假设p为f的左孩子,则 (1)若p为叶结点,即pL和pR均为空.直接删除不会影响树结构; (2)若p只有pL或只有pR.只要令pL或pR直接成为其双亲结点f的左孩子即可,这样也不会影响树结构; 计算机软件技术基础 第四章 树形结构

42 5. 删除二叉排序树上的结点 (3)若p有pL也有pR.为保持中序遍历二叉树的序列不变,可以有两种处理方法:
其一是令pL为f的左子树,pR为s的右子树(s为中序遍历pL的最后一个结点); 其二是令p的直接前驱s替代p,然后删除直接前驱s.若s有左孩子则左孩子取代s的位置。这样虽然影响了树结构,但不会影响中序遍历二叉树时的结点次序. 一般采用第二种方法 计算机软件技术基础 第四章 树形结构

43 5. 删除二叉排序树上的结点 F F PL SL SL F P S C C PR C PR Q S CL CL Q CL S QL QL
计算机软件技术基础 第四章 树形结构

44 5. 删除二叉排序树上的结点 void deleteNode(bitree &*BT, bitree *p, bitree *f){
// 删除二叉排序数BT的结点p，f为p的双亲 bitree *s, *q, *r=p; // s为p的直接前驱，q为s的双亲 if(!p->lchild){ // p的左子树为空 s=p->rchild; delete p; }else if(!p->rchild){// p的右子树为空 s=p->lchild; delete p; }else{ // p的左右子树均不为空 // 查找p的直接前驱s及s的双亲q q=p; s=p->lchild; while(!s->rchild){ q = s; s = s->rchild; } 计算机软件技术基础 第四章 树形结构

45 5. 删除二叉排序树上的结点 // s是p的前驱，由p左右子树均非空，可得s的右子树为空
// 如果p是s的双亲，s是p的左孩子；否则，s是q的右孩子 if(q==p) q->lchild=s->lchild; else q->rchild=s->lchild; p->data = s->data; // 用s代替p delete s; // 删除结点s s = p; // s为当前要链入f的结点 } if(!f) BT = s; // p为根结点，需改变BT else if(f->lchild==r) f->lchild = s; // 如果p为f的左孩子 else f->rchicd = s; 计算机软件技术基础 第四章 树形结构

46 六、哈夫曼树与哈夫曼算法 1、哈夫曼树 1 7 6 4 5 3 2 (a) 8 (b) 哈夫曼树又称最优树，它是一类带权路径长度最短的树。
1）树的路径长度：从树中一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。 树的路径长度是从树根到每一个结点的路径长度之和。路径长度用PL表示，上图中两棵树的路径长度分别是： (a) PL= =17 (b) PL=0+1*2+2*4+3=13 计算机软件技术基础 第四章 树形结构

47 六、哈夫曼树与哈夫曼算法 2）树的带权路径长度：结点带权路径长度为从该结点到树根之间的路径长度与该结点上权值的乘积。树的带权路径长度为树中叶子结点的带权路径长度之和，记作： 其中，wi为树中每个叶子结点的权值，li为每个叶子结点到根结点的路径长度。 计算机软件技术基础 第四章 树形结构

48 六、哈夫曼树与哈夫曼算法 下图3棵二叉树的WPL分别是： a b c d (a) WPL=7*2+5*2+2*2+4*2=36
7 5 4 2 (a) WPL=7*2+5*2+2*2+4*2=36 (b) WPL=7*3+5*3+2*1+4*2=46 (c) WPL=7*1+5*2+2*3+4*3=35 (WPL最小) 3）哈夫曼树 带权路径长度达到最小的二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 计算机软件技术基础 第四章 树形结构

49 六、哈夫曼树与哈夫曼算法 a b c d 7 5 2 4 c d a b 7 5 6 b c d a 7 11 a b c d 18
c 2 d 4 a b b 5 c 2 d 4 a 7 11 a b 7 5 c 2 d 4 18 六、哈夫曼树与哈夫曼算法 2、哈夫曼算法 ① 由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树只有一个权值为Wi的根结点； ② 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和； ③ 将新二叉树加入F中，并去除原两棵树 ④ 重复②、③，直到F中只含一棵树。 计算机软件技术基础 第四章 树形结构

50 2、哈夫曼算法 哈夫曼树的特点: 没有度为1的结点，数据都在叶子结点上。 n个数据的哈夫曼树共有2n-1个结点。 哈夫曼树结点类型:
struct htnode{ elemtype data; // 结点的数据 int weight; // 结点的权值 int parent; // 双亲结点在数组中的下标 int lchild; // 左孩子结点的下标 int rchild; // 右孩子结点的下标 }; htnode hTree[MAXSIZE]; // 存储哈夫曼树的数组 计算机软件技术基础 第四章 树形结构

51 2、哈夫曼算法 // 构成权值为w[1]…w[n]的哈夫曼树，存放在hTree中
// hTree[0]不使用，叶子结点存在hTree[1]…hTree[n]中 void Huffman(htnode hTree[], int w[], int n){ int i,j,k; for(i=1; i<=n; i++){ // 初始化叶子结点 hTree[i].weight = w[i]; hTree[i].parent=0; hTree[i].lchild = 0; hTree[i].rchild=0; } for(;i<=2*n-1;i++) // 初始化非叶结点 hTree[i].parent=0; 计算机软件技术基础 第四章 树形结构

52 2、哈夫曼算法 for(k=n+1; k<=2*n-1; k++){ // 循环生成非叶结点，存放在hTree[k]中
select(hTree,k-1,i,j); // 从结点1至k-1中，选取待合并结点下标至i,j hTree[k].weight=hTree[i].weight+hTree[j].weight; // 合并生成新结点；以下修改指针域 hTree[k].lchild = i; hTree[k].rchild = j; hTree[i].parent = k; hTree[j].parent = k; } 计算机软件技术基础 第四章 树形结构

53 2、哈夫曼算法 // 从结点1至m中选取出双亲为0且权值最小的两个， // 将其下标放到i,j中返回
void select(htnode hTree[],int m, int &i,int &j){ hTree[0].weight = MAXINT; // 设置监视哨 for(i=0,k=1; k<=m; k++) // 查找最小权值结点，下标存入i if(hTree[k].parent==0&& hTree[k].weight<hTree[i].weight) i=k; for(j=0,k=1;k<=m;k++) // 查找次小权值结点，下标存入j if(k!=i&&hTree[k].parent==0&& hTree[k].weight<hTree[j].weight) j=k; } 计算机软件技术基础 第四章 树形结构

54 2、哈夫曼算法 例：八种字符,其频率分别为: 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11 HT.weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 HT.weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 3 23 11 1 7 8 29 14 计算机软件技术基础 第四章 树形结构

55 六、哈夫曼树与哈夫曼算法 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 <
3、哈夫曼树的应用 最佳判定树 WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 不及格 及格 中 良 优 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 ≥ < 计算机软件技术基础 第四章 树形结构

56 六、哈夫曼树与哈夫曼算法 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 <
不及格 及格 中 良 优 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 ≥ < 最优判定树 WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = = 2.25 计算机软件技术基础 第四章 树形结构

57 六、哈夫曼树与哈夫曼算法 哈夫曼编码 哈夫曼编码是可变字长编码(VLC)的一种。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损压缩。一般用来压缩文本和程序文件。 它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期 望长度降低，从而达到无损压缩数据的目的）。 计算机软件技术基础 第四章 树形结构

58 六、哈夫曼树与哈夫曼算法 例：八种字符,其频率分别为: 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11 5
1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 1 0 HC 计算机软件技术基础 第四章 树形结构