[计算机软件及应用]数据结构第6章.ppt

数据结构,常静 Email: ,第六章 树和二叉树,第六章 树和二叉树,树的例子（1）：,第一节 树的定义,树的例子（2）：,第一节 树的定义,1树的定义 树(Tree)是n(n0)个有限数据元素的集合。 (1)当n0时，称这棵树为空树。在一棵非空树T中： (2) 在n0时，有且仅有一个特殊的数据元素称为树的根结点，根结点只有后继结点，没有前驱结点。 (3) 若n1，除根结点之外的其余数据元素被分成m(m0)个互不相交的集合T1，T2，Tm，其中每一个集合Ti(1im)本身又是一棵树。树T1，T2，Tm称为这个根结点的子树。,第一节 树的定义,下面列出一些树结构和非树结构的示意图：,第一节 树的定义,2. 树的表示方法 1) 直观表示法（a） 树的直观表示法是以倒着的分支树的形式表示。 2) 嵌套集合表示法(b) 3) 凹入表示法(c) 4) 广义表表示法(d),（a）,（b）,（d）,（c）,第一节 树的定义,对比树型结构和线性结构的结构特点,第一节 树的定义,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),结点（node）：树中的每个元素及指向其子树根的分支。 结点的度（degree of node）：一个结点的子树个数。 终端结点（terminal node）(叶子（leaf ) ）：度为0的结点。 非终端结点（nonterminal node）（分支结点）：度不为0的结点。 树的度（degree of tree）：树内各结点的度的最大值。 结点的层次（level）：根为第一层，依次类推。 树的深度（depth）（高度（height）：树中结点的最大层次 有序树：树中结点的子树是有次序的。 无序树：树中结点的子树是无次序的。,第二节 基本术语,在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 孩子（child）和双亲（parent）：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 兄弟（sibling）：同一个双亲的孩子之间互为兄弟。 堂兄弟：双亲在同一层的结点互为堂兄弟。 祖先（ancestor）：从根结点到该结点路径上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。,第二节 基本术语,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林,森林（Forest）：,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,ADT Tree 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系R为空集； 否则 R=H， (1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱； (2) 当n1时，其余数据元素可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 H,i=1,2,m。,第三节 树的抽象数据类型,基本操作： 结构初始化 InitTree( 初始条件：树 T 存在。 操作结果：销毁树 T。,第三节 树的抽象数据类型,TreeEmpty(T); 初始条件：树 T 存在。 操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。 Root(T); 初始条件：树 T 存在。 操作结果：返回 T 的根。 Value(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：返回 cur_e 的值。,第三节 树的抽象数据类型,Parent(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是T的非根结点，则返回它的双亲，否则返回“空“。 LeftChild(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是T的非叶子结点，则返回它的最左孩子，否则返回“空“。 RightSibling(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回“空“。 TraverseTree(T, visit(); 初始条件：树T存在，visit 是对结点操作的应用函数。 操作结果：按某种次序对 T 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失败，则操作失败。,Assign(T, cur_e, value); 初始条件：树T存在，cur_e 是 T 中某个结点。 操作结果：结点 cur_e 赋值为 value。 ClearTree( 初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 ADT Tree,第六章 树和二叉树,第一节 二叉树的定义,定义：二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R=H： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 ，它是 root 的“左后继“(H)，如果右子树 R 不空，则必存在一个根结点 为 root 的“右后继“(H)。,第一节 二叉树的定义,基本操作： 结构初始化 InitBiTree( 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T。,第一节 二叉树的定义,BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。 BiTreeDepth(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的根。 Value(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的值。,第一节 二叉树的定义,Parent(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空“。 LeftChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左孩子。若 e 无左孩子，则返回“空“。 RightChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的右孩子。若 e 无右孩子，则返回“空“。 LeftSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回“空“。,RightSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 的结点。 操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回“空“。 PreOrderTraverse(T, visit(); 初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 InOrderTraverse(T, vsit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。 PostOrderTraverse(T, visit(); 初始条件：二叉树T存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。,第一节 二叉树的定义,LevelOrderTraverse(T, visit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 ClearBiTree( 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：结点 e 赋值为 value。,第一节 二叉树的定义,InsertChild( 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 ADT BinaryTree,第一节 二叉树的定义,性质1 在二叉树的第 i 层上至多有 2i-1 个结点(i1)。 性质2 深度为k的二叉树中至多含有 2k-1 个结点，(k1)。 性质3 对任何一棵二叉树 T，如果其终端结点数为n0，度为2的结点数为n2，则n0 =n2+ 1,第二节 二叉树的性质,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,注意编号规则,满二叉树,完全二叉树,特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。,第二节 二叉树的性质,性质4 ： 具有 n 个结点的完全二叉树的深度为 log2 n +1,第二节 二叉树的性质,假设n=4, log2 n +1= log2 4 +1=3,假设n=7, log2 n +1= log2 7 +1=4,性质 5,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点（性质1可由性质2，3推出，证明略）： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,第二节 二叉树的性质,1,2,3,4,5,6,7,8,9,10,11,12,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,一、 二叉树的顺序存储表示,第三节 二叉树的存储结构,例如:,A,B,C,D,F,A B C D E F,0 1 2 3 4 5,2,5,1,3,6,编号i,下标i-1,第三节 二叉树的存储结构,E,4,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,2,5,1,14,3,7,编号i,下标i-1,第三节 二叉树的存储结构,1、二叉链表 2、三叉链表,二、 二叉树的链式存储表示,第三节 二叉树的存储结构,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1. 二叉链表,第三节 二叉树的存储结构,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:,第三节 二叉树的存储结构,A,D,E,B,C,F,root,2三叉链表,parent lchild data rchild,结点结构:,第三节 二叉树的存储结构,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,第三节 二叉树的存储结构,第六章 树和二叉树,按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。,遍历二叉树：,第一节 遍历二叉树,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先（根）序的遍历算法：,第一节 遍历二叉树,A B C D F E G,算法的递归描述,Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraverse,第一节 遍历二叉树,A,B,C,D,E,F,G,D L R,T,D L R,D L R,A,B,E,D L R,D L R,DLR,DLR,C,F,D,G,先序遍历结果:,A,B,C,D,E,F,G,T,若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。,中（根）序的遍历算法：,第一节 遍历二叉树,C B D F A G E,算法的递归描述,Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /InOrderTraverse,第一节 遍历二叉树,A,B,C,D,E,F,G,L D R,T,L D R,L D R,A,B,E,L D R,L D R,LDR,LDR,C,F,D,G,中序遍历结果:,B,D,C,A,G,F,E,T,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后（根）序的遍历算法：,第一节 遍历二叉树,C F D B G E A,算法的递归描述,Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,Visit) if (Visit(T-data) return OK; return ERROR; else return OK; /PostOrderTraverse,第一节 遍历二叉树,A,B,C,D,E,F,G,H,K,例如:,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,第一节 遍历二叉树,例： 已知结点的先序序列和中序序列，求整棵二叉树。,先序序列：A B C D E F G 中序序列：C B E D A F G,第一节 遍历二叉树,构造二叉链表表示的二叉树的递归算法,Status CreateBiTree(BiTree /CreateBiTree,第一节 遍历二叉树,ch,构造二叉链表,按下列次序输入字符: ABC# # DE # G # # F # # # (其中#表示空格字符) 可建立如右图的二叉链表.,第一节 遍历二叉树,遍历是非线性结构的线性化操作保留遍历过程的顺序信息。 线索二叉树的表示: 若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱； 若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。,第二节 线索二叉树,线索二叉树结点的结构:,0 lchild域指示其左孩子 ltag = 1 lchild域指示其前驱 0 rchild域指示其右孩子 rtag = 1 rchild域指示其后继 线索二叉树 线索化 线索链表 线索,第二节 线索二叉树,中序线索二叉树,NIL,NIL,第二节 线索二叉树,a+b*c-d-e/f,中序线索二叉树,第二节 线索二叉树,a+b*c-d-e/f,中序线索二叉树中查找结点的后继和前驱:,如何在中序线索二叉树中找结点的后继： rtag = 1时，rchild所指的结点即为后继； rtag =0时，其后继为遍历其右子树时的第一个结点（最左下结点）。 如结点 “*”的后继是“c” 。 如何在中序线索二叉树中找结点的前驱： ltag = 1时，lchild所指的结点即为前驱； ltag = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。 如根结点 “-”的前驱是“d” 。,第二节 线索二叉树,例如: 将下列二叉链表改为中序线索链表,1 2 3 4 5 6 7 8 9 10 11 12 13 14,第二节 线索二叉树,0 0 0 1 0 1 0 1 0 0 1 1 1 1,5,上例树的形态,1 2 3 4 5 6 7 8 9 10 11 12 13 14,中序线索二叉树,/ 二叉树的二叉线索存储表示 typedef enum Link,Thread PointerTag; /Link=0:指针,Thread=1:线索 typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指针 PointerTag LTag,RTag; /左右标志 BiThrNode, *BiThrTree;,第二节 线索二叉树,中序遍历二叉树T，并将其中序线索化: (为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre),Status InOrderThreading(BiThrTree /InOrderThreading,第二节 线索二叉树,中序遍历进行中序线索化,void InThreading(BiThrTree p) / 一个全程指针pre if (p) InThreading(p-lchild); /左子树线索化 if (!p-lchild) p-LTag=Thread;p-lchild=pre; /前驱线索 if (!pre-rchild) pre-RTag=Thread; pre-rchild=p; /后继线索 pre=p; /保持pre指向p的前驱 InThreading(p-rchild); /右子树线索化 /InThreading,第二节 线索二叉树,第六章 树和二叉树,一、双亲表示法（顺序存储）,* 便于涉及双亲的操作； * 求结点的孩子时需要遍历整棵树。,第一节 树的存储结构,/-树的双亲表存储表示-/ #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; /双亲位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int r，n; /根的位置和结点数 PTree;,第一节 树的存储结构,* 便于涉及孩子的操作；求双亲不方便； * 采用同构的结点，空间浪费。,第一节 树的存储结构,二、孩子表示法（顺序存储）,二、孩子表示法（顺序存储）,#define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int child1; /第1个孩子位置域 int child2; /第2个孩子位置域 int childd; /第d个孩子位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数 PTree;,第一节 树的存储结构,孩子链表存储表示,* 便于涉及孩子的操作； * 求结点的双亲时不方便。,T.nodes ; T.n=10; T.r = 0;,第一节 树的存储结构,孩子链表存储表示（链式存储）,typedef struct CTNode /孩子结点 int child; struct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild; /孩子链表头指针 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; /结点数和根的位置 CTree;,第一节 树的存储结构,三、孩子兄弟表示法 -树的二叉树表示法(二叉链表示法),/-树的二叉链表(孩子兄弟)存储表示- typedef struct CSNode ELemType data; struct CSNode *firstchild,*nextsibling; CSNode, *CSTree;,第一节 树的存储结构,孩子兄弟表示法示例：,第一节 树的存储结构,森林（Forest）：,是m（m0）棵互 不相交的树的集合,B,C,D,E,F,G,H,I,J,M,K,L,一、森林转换成二叉树,如果F=T1,T2, ,Tm是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1=T11,T12, ,T1m1转换而成的二叉树; 其右子对RB是从森林F=T2,T3, ,Tm 转换而成的二叉树.,第二节 森林与二叉树的转换,二、 二叉树转换成森林,如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F=T1,T2, ,Tm： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林 F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林F=T2,T3, ，Tm是由B的右子树RB转换而成的森林。,第二节 森林与二叉树的转换,树的两种遍历方法： 一、先根遍历： （1）访问树的根结点； （2）依次先根遍历每棵子树。 R A D E B C F G H K 二、后根遍历： （1）依次后根遍历每棵子树。 （2）访问树的根结点； D E A B G H K F C R,第三节 树和森林的遍历,森林的两种遍历方法：,一、先序遍历森林： 若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林； （3）先序遍历除去第一棵树之后的森林。 二、中序遍历森林： 若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林； （2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。,第三节 树和森林的遍历,第六章 树和二叉树,最优二叉树(赫夫曼树),路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。 树的路径长度: 树的路径长度是从树根到每一结点的路径长度之和。,第一节 赫夫曼树及其应用,树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径长度kk之和, 通常记作： n WPL= kk。 k=1,第一节 赫夫曼树及其应用,WPL=7x3+5x3+2x1+4x2 = 46,例：下面两棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4,(a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x1+5x2+2x2+4x2 = 35,第一节 赫夫曼树及其应用,最优二叉树的定义,假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为i, 则其中： 带权路径长度WPL最小的二叉树称做最优二叉树，或赫夫曼树,第一节 赫夫曼树及其应用,例下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4,(a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35,第一节 赫夫曼树及其应用,(a)WPL=10x4+30x4+40x3+15x2+5x1=315,第一节 赫夫曼树及其应用,(b)WPL=5x3+15x3+40x2+30x2+10x2=220,构造赫夫曼树的算法思想,(1) 根据给定的n个权值w1,w2, ,wn构成n棵二叉树的集合F=T1,T2, ,Tn，其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子树均空。 (2) 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和。 (3) 在F中删除这两棵树,同时将新得到的二叉树加入F中。 (4) 重复(2)和(3),直到F只含一棵树为止。这棵树便是赫夫曼树。,第一节 赫夫曼树及其应用,构造赫夫曼树举例,第一节 赫夫曼树及其应用,例题：,第一节 赫夫曼树及其应用,构造赫夫曼树,在电文传输中，需要将电文中出现的每个字符进行二 进制编码。在设计编码时需要遵守两个原则： （1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样； （2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。,第二节 赫夫曼编码,1、等长编码：每个字符的编码长度相同。 设字符集只含有4个字符A，B，C，D，用两位二进制表示的编码分别为00，01，10，11。若现在电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。 这种编码的特点: 译码简单且具有唯一性，但编码长度并不是最短的。,第二节 赫夫曼编码,2、不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的。 使用频度较高的字符分配一个相对比较短的编码， 使用频度较低的字符分配一个比较长的编码。,第二节 赫夫曼编码,例如，可以为A、B、C、D四个字符分别分配0，00， 1，01，并可将上述电文用二进制序列：000011010发 送，其长度只有9个二进制位。 但随之带来了一个问题，接收方接到这段电文后无 法进行译码，因为无法断定前面4个0是4个A，1个B加 2个A，还是2个B，即译码不唯一，因此这种编码方法 不可使用。,第二节 赫夫曼编码,ABACCDA,2、不等长编码,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。称为赫夫曼编码。,赫夫曼编码,第二节 赫夫曼编码,（1）利用字符集中每个字符的使用频率作为权值构造一个赫夫曼树； （2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。,赫夫曼编码的构造方法 ：,第二节 赫夫曼编码,例如：,假设有一个电文字符集中有8个字符，每个字符 的使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23, 0.03,0.11，现以此为例设计赫夫曼编码。 为方便计算，将所有字符的频度乘以100，使 其转换成整型数值集合，得到5,29,7,8,14,23, 3,11； 赫夫曼编码设计如下图：,第二节 赫夫曼编码,11,5,29,7,8,14,23,3,100,0,1,15,58,29,0,0,0,1,1,1,8,42,19,0,0,0,1,1,1,00,010,0110,0111,1110,1111,110,10,赫夫曼树的存储结构,用一个大小为2n-1的向量来存储赫夫曼树中的结点， 其存储结构为： typedef struct /结点类型 int weight； /权值，不妨设权值均大于零 int lchild，rchild，parent； /左右孩子及双亲指针 HTNode，*HuffmanTree;/动态分配数组存储树 Typedef char *Huffmancode; ; /动态分配数组存储赫夫曼编码表,第二节 赫夫曼编码,Weight parent lchild rchild,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0 1 2 3 4 5 6 7,W,5,29,8,7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,23,3,11,9,9,9,1,7,8,10,10,3,4,15,11,11