首页计算机计算机基础程序设计基础与数据结构 07 第六章 树.pptx

07 第六章 树.pptx

页数:57页文件大小:339.1 KB来源: 程序设计基础与数据结构ppt课件

本课件系统讲解树型结构:先由实例给出树的定义与基本术语,介绍双亲表示法、孩子表示法与孩子兄弟表示法三种存储方式;随后重点展开二叉树的定义、五条基本性质、顺序与链式存储及基本操作实现;再系统讲解先根、中根、后根与层次四种遍历及线索二叉树,最后介绍树与二叉树的转换和赫夫曼树的构造与应用。

第六章树章节目录页,列出树的基本概念、树的存储表示、二叉树、二叉树的遍历、线索二叉树、树与二叉树转换及赫夫曼树等小节
树的定义说明页,给出树是有限非空数据元素集合、根结点与互不相交子树的递归定义,并配六结点树形结构示意
六结点树结构示例页,展示根结点A与三个互不相交子树T1={B,E,F}、T2={C}、T3={D}的划分关系
查看本课件的文字版(共 57 页,供检索与复制)

第1页:第六章 树章节目录

第六章 树,本章各小节:

  • 6.1 树的基本概念
  • 6.2 树的存贮表示
  • 6.3 二叉树
  • 6.4 二叉树的遍历
  • 6.5 线索二叉树
  • 6.6 树与二叉树的转换
  • 6.7 赫夫曼树
  • 6.8 小结

第2页:树的定义

6.1 树的基本概念:树 T 是一个有限的非空数据元素集合,该集合中的一个特定的数据元素被称为根,其余的数据元素被划分成为若干个互不相交的集合 T1、T2、…、Tm,其中的每个集合都是一棵树,它们也被称为根结点的子树。

图中示例为一棵包含 6 个结点 A、B、C、D、E、F 的树。

第3页:六结点树结构示例

树中包含了 6 个结点,T = {A,B,C,D,E,F}。

  • 结点 A 是树的根结点;
  • 除 A 之外的 5 个结点又分为 3 个不相交的集合 T1、T2、T3,其中 T1 = {B,E,F},T2 = {C},T3 = {D};
  • 它们分别是 A 的 3 棵子树,T1、T2、T3 本身分别也是一棵树。

第4页:树的结点与度

树中的每个数据元素被表示成一个结点,结点与它的子树之间由分枝相连,一个结点不仅包括数据元素的值,还包括指向它的子树的分枝。

孩子结点与双亲
分枝所指向的子树的根,被称为该结点的孩子结点,该结点也就是它的孩子结点的双亲。
兄弟
具有同一个双亲的孩子结点互称为兄弟。
祖先与子孙
结点的祖先指从树的根出发到达此结点所经历的分枝上的所有结点;以该结点为根的子树中的所有结点称为它的子孙。
结点的度与树的度
结点所拥有的分枝数目称为该结点的度,树中各结点的度的最大值称为树的度。
叶子结点与分枝结点
度为 0 的结点称为叶子结点或终端结点;度不为 0 的结点称为分枝结点或非终端结点。

第5页:结点的层次与树的深度

结点的层次从根开始计算:树中根结点的层次为 1,根的孩子结点的层次为 2,也就是说,结点的层次等于它的双亲结点的层次数加 1。

树中结点的最大层次称为树的深度或高度。

第6页:有序树与森林

有序树与无序树
如果把一棵树中的结点的各个子树看作是从左至右有次序的,则称该树为有序树,否则为无序树。对于有序树来说,交换结点的子树次序就构成不同的树。
第一个孩子与最后一个孩子
一般把有序树中的子树进行排序,把有序树中最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。
森林
互不相交的树的集合就构成了森林;对树中的结点而言,其子树的集合就是森林。

第7页:树的基本操作

树的基本操作:

  1. 初始化:构造一棵空树。
  2. 销毁:销毁一棵已存在的树。
  3. 求深度:求出一棵已存在的树的深度。
  4. 求根:取得一棵树的根结点。
  5. 求双亲:取得树中某个结点的双亲结点。
  6. 求孩子:取得树中某个结点的特定孩子结点。
  7. 求右兄弟:取得树中某个结点的右兄弟结点。
  8. 插入:向树中特定位置插入以某个结点为根的子树。
  9. 删除:删除树中以某个结点为根的子树。
  10. 遍历:按指定的顺序依次访问树中的每个结点一次。

说明:原文序号出现两个「6」(求双亲与求孩子),此处已顺次重排为 1~10,操作内容未改动。

第8页:树的存储表示导览

6.2 树的存贮表示,本节的几种表示法:

  • 其他表示法
  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

第9页:树的其他表示法

6.2 树的存贮表示(其他表示法):本节除双亲表示法、孩子表示法与孩子兄弟表示法之外,还可根据实际需要采用其他形式来表示树中的结点与分枝关系。

本页源文件仅保留标题文字,图例部分建议对照原课件图片查看。

第10页:双亲表示法

6.2.1 双亲表示法:树中的每个结点都只有一个唯一的双亲结点,因此在结点中只设一个指向双亲的位置域即可。

#define NODE_NUM 100 typedef struct node_st { char data; int parent; } NODE; NODE tree[NODE_NUM]; 
树的双亲表示法示例
下标dataparent
0A-1
1B0
2C0
3D0
4E1
5F1

说明:表格中的下标、data 与 parent 三列由原文「0A-11B02C03D04E15F1」按示例树的父子关系(A 为根,B、C、D 为 A 的孩子,E、F 为 B 的孩子)切分还原,建议对照原课件图片核对。

第11页:孩子表示法:多重指针域

6.2.2 孩子表示法:树中的每个数据元素都用一个结点来表示,每个结点有多个指针域,指针域的个数依赖于树中该结点的孩子的个数。

结点形式为 data | child1 | child2 | … | childn;图中给出了示例树各结点(A~F)的孩子指针域及空指针的示意。

第12页:带度数的孩子表示法

带 degree 的表示法:以树的度作为孩子指针数组的维数,结点中增设度域。

#define TREE_DEGREE ... typedef struct node_st { char data; struct node_st *child[TREE_DEGREE]; } NODE;

此时的树就可定义为一个指向树的根结点的指针:NODE *tree;

结点形式为 data | degree | child1 | child2 | …。由于各个结点之间不同构,操作起来比较困难,所以也不常用。

第13页:孩子链表表示法

孩子链表表示法:为每个结点建立一条孩子链表,树结点中只保存指向孩子链表表头的指针。

typedef struct childnode_st { int id; struct childnode_st *next; } CHILDNODE; typedef struct node_st { char data; CHILDNODE *firstchild; } NODE; NODE tree[NODE_NUM]; 

图中给出了示例树各结点(下标 0~5,data 为 A~F)的孩子链表连接关系。

第14页:带双亲的孩子链表

带双亲的孩子链表表示法:在孩子链表表示法的树结点中再增加一个双亲位置域。

typedef struct childnode_st { int id; struct childnode_st *next; } CHILDNODE; typedef struct node_st { char data; int parent; CHILDNODE *firstchild; } NODE; NODE tree[NODE_NUM]; 

图中同时给出了 parent、下标、data 与 firstchild 四部分的对应关系。

第15页:孩子兄弟表示法

6.2.3 孩子兄弟表示法:树的结点除了结点信息外,还包括两个指针域,分别指向该结点的第一个孩子结点和下一个兄弟结点。

因为树中的每个结点中有两个指针域,所以又称为二叉链表表示法。

第16页:孩子兄弟表示法类型定义

孩子兄弟表示法的存储结构定义:

typedef struct node_st { char data; struct node_st *child, *brother; } NODE; NODE *tree; 

图中给出了示例树按孩子兄弟表示法连接后的二叉链表形态。

第17页:二叉树章节导览

6.3 二叉树,本节内容包括:

  • 二叉树的定义
  • 二叉树的性质
  • 二叉树的存贮表示

第18页:二叉树的定义

6.3.1 二叉树的定义:二叉树是一个数据元素的有限集(可为空)。当二叉树不空时,它有一个特定的根结点,其余的结点被划分成为两棵互不相交的二叉树,即它的左子树和右子树。

二叉树与树的主要区别
树不能为空,至少要有一个结点,而二叉树可以是一棵空树;
二叉树中的每个结点至多有两个孩子,但树中每个结点可以有任意多个孩子;
二叉树是一棵有序树,每个结点的子树都有左右之分,即使某个结点只有一棵子树,也要区分左右,而在树中,子树是无序的。

第19页:二叉树的五种基本形态

二叉树的五种基本形态:

  • 空二叉树;
  • 只有一个根结点的二叉树;
  • 只有左子树的二叉树;
  • 只有右子树的二叉树;
  • 左、右子树均非空的二叉树。

说明:原文该页仅有标题,五种形态以课件图片为准,此处按标题作文字整理。

第20页:二叉树的基本操作

二叉树的基本操作:

  1. 初始化:构造一棵空的二叉树。
  2. 销毁:销毁一棵已存在的二叉树。
  3. 求深度:求出一棵已存在的二叉树的深度。
  4. 求根:取得一棵二叉树的根结点。
  5. 求双亲:取得二叉树中某个结点的双亲结点。
  6. 求左孩子:取得二叉树中某个结点的左孩子结点。
  7. 求右孩子:取得二叉树中某个结点的右孩子结点。
  8. 求左兄弟:取得二叉树中某个结点的左兄弟结点。
  9. 求右兄弟:取得二叉树中某个结点的右兄弟结点。
  10. 插入:向二叉树中特定位置插入以某个结点为根的左子树或右子树。
  11. 删除:删除二叉树中以某个结点为根的左子树或右子树。
  12. 遍历:按指定的顺序依次访问二叉树中的每个结点一次,通常有 4 种方式:先根序、中根序、后根序及层次遍历。

说明:原文序号中「求双亲」与「求左孩子」均标为 6,此处已顺次重排,操作内容未改动。

第21页:表达式的二叉树表示

用二叉树表示算术表达式:表达式 a + b * c - d / e 对应的二叉树中,根结点为运算符「-」,其左子树为「+」与「*」构成的 a + b * c,右子树为「/」构成的 d / e。

分支结点存放运算符,叶子结点(a、b、c、d、e)存放操作数,运算次序由结点的层次决定。

第22页:二叉树的性质(一)

6.3.2 二叉树的性质:

性质 1
一棵具有 n 个结点的二叉树必有 n-1 条分枝。树中每个结点(除根结点外)都只有一个双亲,而在每个结点与其双亲之间只有一条分枝相连,根结点无双亲,故 n 个结点的二叉树必有 n-1 条分枝。
性质 2
二叉树的第 i 层上最多有 2i-1 个结点。i = 1 时,2i-1 = 20 = 1,二叉树的第一层只有一个根结点;若对所有 k(1 ≤ k < i)性质成立,则第 i-1 层上至多有 2i-2 个结点,第 i 层上就有 2 × 2i-2 = 2i-1 个结点。
性质 3
假设高度为 h 的二叉树的结点数为 n,则 h ≤ n ≤ 2h-1。二叉树中每层至少有 1 个结点,故 h ≤ n;而高度为 h 的二叉树的最大结点数为各层最大结点数之和,即 2h-1。

第23页:满二叉树与完全二叉树

性质 4:假设具有 n 个结点的二叉树的高度为 h,则 n ≥ h ≥ ⌈log2(n+1)⌉。

  • 每层至少有 1 个结点,故树的高度不可能超过 n;由性质 3 知 n ≤ 2h-1,所以 h ≥ log2(n+1),又 h 为整数,故 h ≥ ⌈log2(n+1)⌉。
  • 高度为 h 且正好包含 2h-1 个结点的二叉树称为满二叉树。
  • 把高度为 h 的满二叉树按层次从上到下、从左至右地编号为 1 至 2h-1,则高度为 k、有 n 个结点的二叉树,当且仅当该树中的每一个结点都与相同深度的满二叉树中前 n 个结点的位置一一对应时,称为完全二叉树。
  • 满二叉树是完全二叉树的特例;完全二叉树是相同结点个数下高度最小的二叉树,具有 n 个结点的完全二叉树的高度为 ⌈log2(n+1)⌉。

第24页:满二叉树与完全二叉树示意

图中给出高度为 3 的满二叉树(结点按层次编号 1~7)与完全二叉树的结点编号示例,用以说明两种形态在最后一层结点排列上的区别。

说明:原文该页主要为图示,编号序列字符粘连,具体编号以课件图片为准。

第25页:完全二叉树的编号关系

性质 5:假设具有 n 个结点的完全二叉树按层次从上到下、从左至右进行编号,则对编号为 i 的结点有:

  1. 如果 i = 1,则结点 i 是二叉树的根结点;如果 i > 1,则其双亲结点的编号为 ⌊i/2⌋;
  2. 如果 2i > n,则结点 i 无左孩子;否则其左孩子结点的编号为 2i;
  3. 如果 2i + 1 > n,则结点 i 无右孩子;否则其右孩子结点的编号为 2i + 1。

该性质的 1 与 2、3 实际上完全等价,故只需知道 2 和 3 就可以得到 1;2、3 可用数学归纳法证明。

第26页:二叉树的存储表示导览

6.3.3 二叉树的存贮表示,两种存储结构:

  • 顺序存储结构
  • 链式存储结构

第27页:二叉树的顺序存储

6.3.3.1 二叉树的顺序存储结构:按完全二叉树的编号次序,用一组连续的存储单元(一维数组)依次存放二叉树中的结点。

图中给出高度为 3 的右单枝树及其存储示意:结点 A、B、C 只占用了与各自编号对应的数组单元,其余大量单元被空置,可见顺序存储对右单枝树这类形态会造成较大的空间浪费。

第28页:二叉链表存储结构

6.3.3.2 二叉树的链式存储结构——二叉链表表示:

typedef struct node_st { char data; struct node_st *left, *right; } NODE; NODE *tree; 

结点由 left | data | right 三个域构成,图中给出了示例二叉树的二叉链表连接示意。

第29页:三叉链表存储结构

三叉链表表示:在二叉链表的基础上再增加一个指向双亲结点的指针域。

typedef struct node_st { char data; struct node_st *left, *right; struct node_st *parent; } NODE;

结点由 left | data | right | parent 四个域构成,图中给出了示例二叉树的三叉链表连接示意。

第30页:二叉树的遍历导览

6.4 二叉树的遍历:按一定的次序,对二叉树中的每个结点访问且仅访问一次。

通过遍历,就使二叉树这种本来非线性的结构映射为一种线性的排列。本节包括:

  • 遍历的递归过程
  • 遍历的非递归过程
  • 遍历的性质

第31页:四种遍历方式导览

6.4.1 遍历的递归过程,四种遍历方式:

  • LDR(中根序)
  • DLR(先根序)
  • LRD(后根序)
  • 层序遍历

第32页:先根序遍历算法

先根序遍历(DLR)的步骤:

  1. 访问根结点;
  2. 先序遍历左子树;
  3. 先序遍历右子树。
int visit(NODE *node); int PreOrderTraverse(NODE *tree) { if (tree != NULL) { visit(tree); PreOrderTraverse(tree->left); PreOrderTraverse(tree->right); } }; 

说明:原文该页页眉标注为「LDR(中根序)」,但所列步骤与函数名 PreOrderTraverse 均为先根序(DLR),此处按步骤与代码内容整理,建议对照原课件图片核对。

第33页:中根序遍历算法

中根序遍历(LDR)的步骤:

  1. 中序遍历左子树;
  2. 访问根结点;
  3. 中序遍历右子树。
int visit(NODE *node); int InOrderTraverse(NODE *tree) { if (tree != NULL) { InOrderTraverse(tree->left); visit(tree); InOrderTraverse(tree->right); } }; 

说明:原文该页页眉标注为「DLR(先根序)」,但所列步骤与函数名 InOrderTraverse 均为中根序(LDR),此处按步骤与代码内容整理,建议对照原课件图片核对。

第34页:后根序遍历算法

后根序遍历(LRD)的步骤:

  1. 后序遍历左子树;
  2. 后序遍历右子树;
  3. 访问根结点。
int visit(NODE *node); int PostOrderTraverse(NODE *tree) { if (tree != NULL) { PostOrderTraverse(tree->left); PostOrderTraverse(tree->right); visit(tree); } }; 

第35页:层序遍历

层序遍历:从根结点开始,按层次从上到下、同一层中从左到右的顺序依次访问二叉树中的每个结点,通常借助队列实现。

说明:原文该页仅保留标题,遍历过程的示例图示建议对照原课件图片查看。

第36页:遍历的非递归实现导览

6.4.2 遍历的非递归过程:虽然二叉树遍历的递归算法比较简单,但是其在实现时由于要进行反复的递归调用,会占用较多的存储空间,花费较多的运行时间,效率较低。

在实际应用时,常常需要将递归算法用非递归的方式实现,即利用栈,将递归过程转化为非递归过程:

  • 先序非递归遍历
  • 中序非递归遍历
  • 后序非递归遍历

第37页:先序非递归遍历

先序非递归遍历:为进行非递归的访问,需要增加一个辅助的栈,用这个栈来实现原来的递归过程。

NODE (*stack)[NODE_NUM]; void PreOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree); while (!EmptyStack(&stack)) { nextp = PopStack(&stack); visit(nextp); if (nextp->right != NULL) PushStack(&stack, nextp->right); if (nextp->left != NULL) PushStack(&stack, nextp->left); } return SUCCESS; }; 

第38页:先序非递归遍历栈状态

本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果三者的对应关系:根结点「-」先入栈,出栈后其右孩子「/」与左孩子「+」依次入栈,如此反复,最终得到先序序列 -+a*bc/de。

说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。

第39页:中序非递归遍历

中序非递归遍历:栈元素中除结点指针外,还需记录该结点的进栈次数。

typedef struct stack_st { NODE *node; int isfirst; } STACK; STACK stack[NODE_NUM]; int PushStack(STACK s[NODE_NUM], NODE *p, int id); int PopStack(STACK s[NODE_NUM], STACK &sp); void InOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree, TRUE); while (!EmptyStack(&stack)) { PopStack(&stack, &next); if (next.isfirst == TRUE) { if (next.node->right != NULL) PushStack(&stack, next.node->right, TRUE); PushStack(&stack, next.node, FALSE); if (next.node->left != NULL) PushStack(&stack, next.node->left, TRUE); } else visit(next.node); } return SUCCESS; }; 

第40页:中序非递归栈状态示例

本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果的对应关系:结点第一次出栈时按先右、再根、后左的次序重新进栈,第二次出栈时才访问,最终得到中序序列 a+b*c-d/e。

说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。

第41页:后序非递归遍历

后序非递归遍历:同样借助记录进栈次数的栈,但进栈次序改为先根、再右、后左,使访问次序为先左、再右、最后根。

 void PostOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree, TRUE); while (!EmptyStack(&stack)) { PopStack(&stack, &next); if (next.isfirst == TRUE) { PushStack(&stack, next.node, FALSE); if (next.node->right != NULL) PushStack(&stack, next.node->right, TRUE); if (next.node->left != NULL) PushStack(&stack, next.node->left, TRUE); } else visit(next.node); } return SUCCESS; }; 

第42页:后序非递归栈状态示例

本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果的对应关系:结点第一次出栈时按先根、再右、后左的次序重新进栈,第二次出栈时才访问,最终得到后序序列 abc*+de/-。

说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。

第43页:遍历的性质

6.4.3 遍历的性质:

性质 1
由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。
性质 2
由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。

第44页:线索二叉树导览

6.5 线索二叉树:通过遍历使二叉树中的结点从一种非线性的序列排列成了线性序列。

通过每个结点的左右孩子指针能够方便地找到结点的左右孩子,却很难找到其前驱和后继。若每个结点再增加两个指针域分别指向前驱与后继,则每个结点将有一个信息域和四个指针域,太浪费存储空间。

在二叉树的二叉链表存储结构中,如果树中的结点个数为 n,那么必有 2n 个指针域,但其中只有 n-1 个有效指针,其余的 n+1 个指针域必为空。一种比较巧妙的方法是利用这 n+1 个空指针域来存放结点的前驱和后继信息;为与指向左右孩子的指针相区别,必须引入标志信息。本节包括:

  • 线索二叉树的定义
  • 线索二叉树的遍历

第45页:线索二叉树的定义

6.5.1 线索二叉树的定义:以结点的左孩子指针指示其左孩子或前驱(设置标志位 lid 来区分),以结点的右孩子指针指示其右孩子或后继(设置标志位 rid 来区分),则结点的结构演变为:

结点形式:lid | left | data | right | rid。

其中指向结点前驱和后继的指针,叫做线索;加上线索的二叉树称为线索二叉树。

第46页:线索二叉树的遍历

6.5.2 线索二叉树的遍历:图中以表达式 a + b * c - d / e 对应的二叉树为例,分别给出先序线索树、中序线索树与后序线索树的线索连接示意。

  • 先序线索树:按先根序的访问次序把空指针域改为指向前驱与后继的线索;
  • 中序线索树:按中根序的访问次序连接线索;
  • 后序线索树:按后根序的访问次序连接线索;
  • 序列首、末结点的空链域以 NIL 表示。

第47页:树与二叉树的转换导览

6.6 树与二叉树的转换,本节包括:

  • 树与二叉树的转换
  • 森林与二叉树的转换
  • 树与森林的遍历

第48页:树转换为二叉树的规则

6.6.1 树与二叉树的转换,对应规则为:

  • 树中的一个结点与二叉树的一个结点相对应;
  • 树中结点的第一个孩子指针所指向的结点,对应于二叉树中该结点的左孩子;
  • 树中结点的第一个兄弟指针所指向的结点,对应于二叉树中该结点的右孩子。

第49页:树与二叉树转换示例

图中给出示例树(结点 A~F)的孩子兄弟链表表示与其对应的二叉树形态:按「第一个孩子作左孩子、第一个兄弟作右孩子」的规则,树中 A 的孩子 B、C、D 在二叉树中沿左、右链依次连接,B 的孩子 E、F 则成为 B 的左子树。

说明:原文该页主要为图示与粘连的字符序列,具体连接关系以课件图片为准。

第50页:森林转换为二叉树

6.6.2 森林与二叉树的转换:森林转化为二叉树的方法为:

  1. 把森林中的每棵树转化为相应的二叉树;
  2. 从最后一棵树开始,把后一棵二叉树的根作为前一棵二叉树根的右孩子连接起来,直到将森林中全部的树连成一棵二叉树。

图中给出了由若干棵树组成的森林转换为一棵二叉树的示例。

第51页:二叉树转换为森林

二叉树转化为森林的方法为:

  1. 把摘除二叉树根结点的右子树后所得到的二叉树转化成森林中的第一棵树;
  2. 将 1 中摘除的右子树转化成森林中其余的树。

通过树、森林与二叉树之间的转换,就可以借助二叉树的运算来实现树与森林的运算。

第52页:树与森林的遍历

6.6.3 树与森林的遍历:树的遍历有两种形式。

先(根)序遍历
(1) 访问森林中第一棵树的根结点;(2) 先序遍历第一棵树中根结点的子树森林;(3) 先序遍历除去第一棵树之后剩余的森林。
后(根)序遍历
(1) 遍历森林中第一棵树的根结点的子树森林;(2) 访问第一棵树的根结点;(3) 遍历除去第一棵树之后剩余的森林。

说明:原文后(根)序遍历的三个步骤中写作「中序遍历」,与标题「后(根)序遍历」不一致,此处按标题与遍历含义整理,建议对照原课件图片核对。

第53页:赫夫曼树导览

6.7 赫夫曼树:赫夫曼树是一棵最优二叉树,其带权路径长度最短。本节包括:

  • 最优二叉树
  • 前缀编码
  • 赫夫曼编码

第54页:最优二叉树与带权路径长度

6.7.1 最优二叉树:

路径与路径长度
两个结点之间的路径由连接这两个结点的分枝所构成,路径上的分枝数目就是路径的长度。
树的带权路径长度
如果二叉树中的 n 片叶子结点带权为 w1, w2, …, wn,且从根到叶子结点的路径长度为 li,那么树的带权路径长度为树中所有叶子结点到树根之间的路径长度与叶子结点上权的乘积之和。
最优二叉树(赫夫曼树)
对于确定的 n 个权值 {w1, w2, …, wn},如果能构造出一棵二叉树,使树中的 n 片叶子结点分别带权为 w1, w2, …, wn,且该树能取到适当的 l1, l2, …, ln,使树的带权路径长度 W 达到最小值,则称这样的二叉树为最优二叉树或赫夫曼树。

第55页:前缀编码

6.7.2 前缀编码:进行不等长编码时,必须保证任何一个字符的编码都不能是其它字符编码的前缀,这样的编码称为前缀编码。

采用前缀编码可以保证译码时不会出现二义性,是设计不等长编码的基本约束。

第56页:赫夫曼编码

6.7.3 赫夫曼编码:为了提高编码的效率,可以利用赫夫曼算法进行前缀编码。

把每个字符的出现频率记为 wi,设其编码长度为 li,则编码总长为 ∑wklk(k = 1…n)。如果设二叉树中的 n 片叶子结点的权值为 w1, w2, …, wn,且从根到叶子结点的路径长度为 li,那么 ∑wklk(k = 1…n)就为树的带权路径长度。

这样,要使前缀编码的总长度最短的问题,就转化成了设计一棵最优二叉树的问题。

第57页:第六章小结

6.8 小结:

  • 树的基本概念:树的定义、基本术语与基本操作;
  • 树的存储表示及其基本操作:双亲表示法、孩子表示法与孩子兄弟表示法;
  • 二叉树:具有良好的数学性质、方便的表示与操作,重要操作包括遍历、线索化等,通过一定的手段可以实现树与二叉树的对应转换,重要的应用是最优二叉树。
顶部目录