《数据结构实用教程(C语言版)》第5章树.ppt

,数据结构实用教程（C语言版） 中国水利水电出版社,第5章 树,本章中主要介绍下列内容： 树的逻辑定义和存储结构 二叉树的逻辑定义、存储结构 二叉树的基本操作算法 树和二叉树的转换 哈夫曼树及其应用,本章目录,结束,5.1 树,5.1.1 树的定义 5.1.2 树的表示方法 5.1.3 树的基本术语 5.1.4 树的存储结构,返回到总目录,5.1.1 树的定义,树是n（n0）个结点的有限集合。当n=0时称为空树。当n0时，是非空树，它满足以下两个条件： （1）有且仅有一个称为根的结点； （2）其余结点分为m（m0）个互不相交的非空集合T1，T2，Tm，其中每个集合本身又是一棵树，称为根的子树。,返回到本节目录,树的二元组表示法,树可用二元组来表示。其中，D为结点集合，R为边的集合。一棵树T如图5-1所示，则它的二元组表示方法为： T=（D,R） D=A,B,C,D,E,F,G,H R=,图5-1 树的逻辑结构图,返回到本节目录,5.1.2树的表示方法,树的逻辑结构表示有树形表示法，文氏图表示法，凹入表示法和广义表表示法等。 1树形表示法 这是树的最基本的表示，使用一棵倒置的树表示树结构。图5-1就是采用这种方法。 2文氏表示法 使用集合以及集合的包含关系描述树结构。图5-2（a）就是图5-1的树的文氏图表示法。 3凹入表示法 使用线段的伸缩关系描述树的结构。图5-2（b）就是图5-1的树的凹入表示法。 4广义表表示法 将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构。图5-2（c）就是图5-1的树的广义表表示法。,返回到本节目录,树的三种表示方法,(a)文氏图表示法 (b)凹入图表示法 (c)广义表表示法 图5-2 树的其它表示方法,返回到本节目录,5.1.3树的基本术语,1结点 树的结点包含一个数据元素及若干指向其子树的分支。 2结点的度 结点所拥有的分支数目或后继结点个数称为该结点的度（Degree）。例如图5-1所示的树中结点A的度为3，结点C的度为2，结点E的度为0。 3树的度 树中各结点度的最大值称为该树的度。例如图5-1所示的树的度为3。 4叶子（终端结点） 度为零的结点称为叶子结点。例如图5-1所示的树中结点E、G、H、I为叶子结点。,返回到本节目录,5.1.3树的基本术语,5分支结点 度不为零的结点称为分支结点。例如图5-1所示的树中的A、B、C、D、F都是分支结点。 6孩子结点 一个结点的后继称为该结点的孩子结点。例如图5-1所示的树中A的孩子结点为B、C、D。 7双亲结点 一个结点称其为其后继结点的双亲结点。例如图5-1所示的树中A是B、C、D的双亲结点，C是F、G的双亲。 8兄弟结点 同一双亲结点下的孩子结点互称为兄弟结点。例如图5-1所示的树中B、C、D互为兄弟结点， F、G互为兄弟结点，但不同双亲的两个同层结点不互为兄弟结点，如G和H不互为兄弟结点。,返回到本节目录,5.1.3树的基本术语,9堂兄弟 双亲互为兄弟的两个结点互称为堂兄弟。例如图5-1所示的树中G和H就互为堂兄弟。 10子孙结点 一个结点的所有子树中的结点称之为该结点的子孙结点。例如图5-1所示的树中A的子孙为B、C、D、E、F、G、H、I。 11祖先结点 从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点。例如图5-1所示的树中E的祖先结点为A和B（包括其双亲结点B）。,返回到本节目录,5.1.3树的基本术语,12层数 树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。例如图5-1所示的树中A的层数为1，B、C、D的层数为2，E、F、G、H的层数为3，I的层数为4。 13树的深度 树中结点的最大层数称为树的深度（或高度）。例如图5-1所示的树中的深度为4。 14有序树和无序树 如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成了不同的树，称这样的树为有序树，反之，则为无序树。 15森林 m（m0）棵互不相交树的集合称为森林。,返回到本节目录,5.1.4 树的存储结构,1.双亲表示法 用一个一维数组存储树中的各个结点，数组元素是一个结构体型数据，包含两个域：data域和parent域，分别表示结点的数据值和其双亲结点在数组中的下标。其类型定义如下： typedef struct ElemType data; /*结点的数据域，ElemType可以是任意类型*/ int parent; /*结点存储其双亲的数组下标值*/ ParTypeMaxSize;,返回到本节目录,1.双亲表示法示例,图5-1中给出的树，可以用图5-3来存储表示。其中，规定数组下标为0的位置存储的是根结点，设根结点的parent域为-1。,图5-3 图5-1中树的双亲表示法,返回到本节目录,5.1.4 树的存储结构,2.孩子表示法 将每个结点的孩子结点构成一个单链表，称之为孩子链表。n个结点的树有n个这样的孩子链表。为了方便起见，我们将每个结点存放在一个顺序表中，顺序表的每个元素有两个域：一个是存放该结点的数据值；另一个是存放该结点的第一个孩子的地址。孩子结点也有两个域：一个域是存放该孩子结点在顺序表中的位置（数组下标），另一个域是存放下一个孩子的地址。,返回到本节目录,2.孩子表示法举例,图5-4是图5-1所示树的孩子表示法。其中，规定表头下标为0的位置存放根结点。,图5-4 图5-1树的孩子表示法,返回到本节目录,5.1.4 树的存储结构,3.孩子兄弟法 孩子兄弟法存储结构是一种二叉链表，链表中每个结点包括三个域：数据值和两个指针，其中一个指针指向该结点的最左边第一个孩子，而另一个指针则指向该结点的下一个兄弟。每个结点的类型定义如下： typedef struct node2 ElemType data; /*数据域*/ Struct node2 *child,*brother; /*其第一个孩子和其右边兄弟的地址*/ CBNodeType; /*孩子兄弟结点类型*/,返回到本节目录,图5-5是图5-1所示树的孩子兄弟表示法的存储结构。其中T指向树的根结点。,图5-5 图5-1树的孩子兄弟表示法,返回到本节目录,5.2 二叉树,5.2.1 二叉树的定义 5.2.2 二叉树的性质 5.2.3 二叉树的存储结构 5.2.4 二叉树的基本运算,返回到总目录,5.2.1 二叉树的定义,1二叉树的定义 二叉树（Binary Tree）是有n（n0）个结点的有限集合。 （1）该集合或者为空（n=0）； （2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树； （3）左子树和右子树同样又都是二叉树。,返回到本节目录,5.2.1 二叉树的定义,2二叉树的形态 二叉树归纳起来有五种形态，如图5-7所示。,(a)空二叉树 (b)只有一个根结点 (c)右子树为空 (d)左子树为空 (e)左、右子树非空 图5-7 二叉树的五种形态,返回到本节目录,5.2.2 二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点（i1）。 性质2：深度为k的二叉树中至多有2k -1个结点。 性质3：对任意一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则有n0=n2+1。,返回到本节目录,5.2.2 二叉树的性质,下面介绍两种特殊的二叉树。 （1）满二叉树 一棵深度为k，且有2k-1个结点的二叉树称为满二叉树。图5-9（a）所示是一棵深度为4的满二叉树，其特点是每一层上的结点都具有最大的结点数。 （2）完全二叉树 在一棵二叉树中，除最后一层外，若其它层都是满的，并且最后一层或者是满的，或者是在右边缺少连续的若干个结点，则称此二叉树为完全二叉树。据此得知满二叉树是完全二叉树的特例。图5-9（b）是一棵深度为4 的完全二叉树。,返回到本节目录,满二叉树和完全二叉树示例,(a)一棵满二叉树 (b)一棵完全二叉树 图5-9 一棵满二叉树和一棵完全二叉树示意图,返回到本节目录,5.2.2 二叉树的性质,性质4：具有n个结点的完全二叉树的深度为。 性质5：如果一棵有n个结点的完全二叉树（其深度为）的结点按层次（从第1层到第层，每层从左到右。则对任一结点i(1in)有： （1）如果i=1，结点i是根结点，无双亲；如果i1，则其双亲结点是结点i/2。 （2）如果2in，则结点i无左孩子，该结点为叶子结点；否则其左孩子是结点2i。 （3）如果2i+1n，则结点i无右孩子，该结点为叶子结点；否则其左孩子是结点2i+1。,返回到本节目录,5.2.3 二叉树的存储结构,1顺序存储结构 顺序存储一棵二叉树时，先对该二叉树中的各结点进行编号，然后以各结点的编号为下标，把各结点的值存到一维数组中。 其编号过程为：首先，把树的根结点的编号定为1，然后按照层次从上到下，从左到右的顺序对每一结点进行编号。当一个结点的双亲结点的编号为i时，若它是左孩子，则编号为2i，若它是右孩子，则编号为2i+1。如图5-10(a)所示的二叉树（各结点上方的数字就是该结点的编号）对应的顺序存储结构为图5-10(b)所示。,返回到本节目录,顺序存储的二叉树示例,一棵带编号的二叉树,(b)对应的顺序存储结构 图5-10 一棵二叉树及其顺序存储结构,返回到本节目录,5.2.3 二叉树的存储结构,2链式存储结构 对于一般的二叉树，通常采用二叉链表示。链表中的每个结点包含两个指针，分别指向该结点的左孩子和右孩子。在二叉树的链式存储结构中，结点的类型定义如下： Typedef struct tnode ElemType data; /*数据域*/ struct tnode *lchild,*rchild; /*左、右孩子指针域*/ BTNode; /*二叉树结点存储类型*/ 其中，data域中存入结点的数据值，lchild和rchild分别表示左指针域和右指针域，分别存储其左、右孩子结点的地址。,返回到本节目录,图5-11 二叉树链式存储结构,如图5-10的二叉树链式存储结构如图5-11所示。,返回到本节目录,5.2.4 二叉树的基本运算,二叉树的常用运算有以下几种： （1）bt=CreateBTree(str):根据二叉树的广义表表示法str建立二叉树bt。 （2）BTHeight(bt)：求一棵二叉树bt的高度。 （3）NodeCount(bt)：求一棵二叉树bt的结点个数。 （4）LeafCount(bt): 求一棵二叉树bt的叶子结点个数。 （5）DispBTree(bt):以广义表表示法输出一棵二叉树bt。,返回到本节目录,5.3 二叉树的建立和遍历,5.3.1 二叉树的建立和输出 5.3.2 二叉树的遍历 5.3.3 由遍历序列恢复二叉树,返回到总目录,5.3.1 二叉树的建立和输出,1二叉树的建立 二叉树的建立是二叉树的重要运算之一，我们介绍的方法是：用字符ch扫描用广义表表示法输入的二叉树的字符串str。分以下几种情况： （1）若ch=(，则将前面刚创建的结点作为双亲结点进栈，并置k=1，表示其后创建的结点将作为这个结点的左孩子结点。 （2）若ch=)，表示栈中结点的左右孩子结点处理完毕，退栈。 （3）若ch=,，表示要创建一个结点，并根据k值建立它与栈中结点之间的联系，当k=1时，表示这个结点作为栈中结点的左孩子结点，当k=2时，表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。算法中使用一个栈st保存双亲结点，top为其栈顶指针，k指定其后处理的结点是双亲结点（保存在栈中）的左孩子结点（k=1）还是右孩子结点（k=2）。,返回到本节目录,1二叉树的建立,（1）二叉树的存储结构及相关类型的定义如下： #define NULL 0 /*定义空指针为0*/ #define MaxSize 100 /*树的最大元素个数为100*/ typedef char ElemType; /*重定义char为ElemType类型 */ typedef struct tnode ElemType data; /*数据域*/ struct tnode *lchild,*rchild; /*左、右孩子指针*/ BTNode; /*二叉树结点类型*/,返回到本节目录,1二叉树的建立算法,（2）二叉树的建立对应的算法如算法5.1所示。 算法5.1 BTNode *CreateBTree(char *str) BTNode *bt,*stMaxSize,*p=NULL; int top=-1,k,j=0; char ch; bt=NULL; ch=strj; while(ch!=0) switch (ch) case (:top+; /*若是左括号，则先入栈*/ sttop=p; k=1; break; case ):top-;break; /*若是右括号，则出栈*/,返回到本节目录,1二叉树的建立算法,case ,:k=2;break; /*若是逗号，则有右子树*/ default : /*若是其它字符，则生成新的二叉树结点*/ p=(BTNode *)malloc(sizeof(BTNode); p-data=ch; p-lchild=p-rchild=NULL; if(bt=NULL) bt=p; else switch(k) case 1:sttop-lchild=p;break; case 2:sttop-rchild=p;break; j+; ch=strj; return(bt); ,返回到本节目录,5.3.1 二叉树的建立和输出,2用广义表表示法输出二叉树 其过程是：对于非空二叉树bt，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个(符号，然后递归处理左子树，输出一个,符号，递归处理右子树，最后输出一个)。对应的算法如算法5.2。,返回到本节目录,2用广义表表示法输出二叉树,算法5.2 void DispBTree(BTNode *bt) if (bt!=NULL) printf(“%c“,bt-data); if(bt-lchild!=NULL) printf(“(“); DispBTree(bt-lchild); if(bt-rchild!=NULL) printf(“,“); DispBTree(bt-rchild); printf(“)“); ,返回到本节目录,5.3.2 二叉树的遍历,一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。 一般限定先左后右的次序，那么只有三种遍历：DLR（根左右）、LDR（左根右）、LRD（左右根）。我们将这三种遍历方法称作前（根）序遍历，中（根）遍历和后（根）序遍历。 也可以对二叉树的每个层次的各结点按从左至右进行遍历（按层次遍历），下面我们分别介绍这几种遍历方法。,返回到本节目录,1.前（根）序遍历二叉树（DLR）,有些教材称为先（根）序遍历。若二叉树为空，遍历结束。否则依次执行以下操作： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 前序遍历的递归算法如算法5.3所示。 以图5-10为例，进行前序遍历的输出序列为：ABDCEGF。,返回到本节目录,前序遍历的递归算法,算法5.3 void PreOrder(BTNode *bt) /* 前序遍历二叉树BT*/ if(bt=NULL) return; /* 递归调用的结束条件*/ else printf(“%c“,bt-data); /* 输出结点的数据域*/ PreOrder(bt-lchild); /*前序递归遍历左子树*/ PreOrder(bt-rchild); /* 前序递归遍历右子树*/ ,返回到本节目录,2.中（根）序遍历二叉树（LDR）,若二叉树为空，遍历结束。否则依次执行以下操作： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 中序遍历的递归算法如算法5.4所示。 以图5-10为例，进行中序遍历的输出序列为：DBAGECF。,返回到本节目录,中序遍历的递归算法,算法5.4 void InOrder(BTNode *bt) /*中序遍历二叉树BT*/ if(bt=NULL) return; /*递归调用的结束条件*/ else InOrder(bt-lchild); /* 中序递归遍历左子树*/ printf(“%c“,bt-data); /*输出结点的数据域*/ InOrder(bt-rchild); /* 中序递归遍历右子树*/ ,返回到本节目录,3后（根）序遍历二叉树（LRD）,若二叉树为空，遍历结束。否则依次执行以下操作： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。 （3）访问根结点； 后序遍历的递归算法如算法5.5所示。 以图5-10为例，进行后序遍历的输出序列为：DBGEFCA。,返回到本节目录,后序遍历的递归算法,算法5.5 void PostOrder(BTNode *bt) /*后序遍历二叉树BT*/ if (bt=NULL) return; /*递归调用的结束条件*/ else PostOrder(bt-lchild); /*后序递归遍历左子树*/ PostOrder(bt-rchild); /*后序递归遍历右子树*/ printf(“%c“,bt-data); /*输出结点的数据域*/ ,返回到本节目录,4层次遍历二叉树,在进行层次遍历时，对某一层的结点访问完后，再按照它们的访问次序对各个结点的左、右孩子顺序访问，这样一层一层进行，先访问的结点其左、右孩子也要先访问。这样的操作与队列的原则比较符合，所以可以用一个环形队列qu来实现。 层次遍历过程是先将根结点进队，在队不空时循环；从队列中出列一个结点*p，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队，直到队空为止。算法如算法5.6所示。 以图5-10为例，进行按层次遍历的输出序列为：ABCDEFG。,返回到本节目录,层次遍历的算法,算法5.6 void LevelOrder(BTNode *bt) BTNode *p; BTNode *quMaxSize; /*定义循环队列，存放结点指针*/ int front,rear; /*定义队头队尾指针*/ front=rear=-1; /*空队*/ rear+; qurear=bt; /*根结点指针进入队列*/,返回到本节目录,层次遍历的算法,while(front!=rear) /*队列不空时*/ front=(front+1)%MaxSize; p=qufront; /*队头出队列*/ printf(“%c“,p-data); if(p-lchild!=NULL) /*有左孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if(p-rchild!=NULL) /*有右孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-rchild; ,返回到本节目录,5.3.3 由遍历序列恢复二叉树,1由前序和中序恢复二叉树 （1）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和右子树； （2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲结点上去； （3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。,返回到本节目录,5.3.3 由遍历序列恢复二叉树,2由中序和后序恢复二叉树 由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为： （1）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树； （2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲（parent）结点上去； （3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。,返回到本节目录,5.4 树、森林与二叉树的转换,5.4.1 树、森林转换为二叉树 5.4.2 二叉树还原为树、森林,返回到总目录,5.4.1 树、森林转换为二叉树,1树转换成二叉树 将一棵树转换成二叉树的过程如下： （1）加线：树中所有相邻兄弟之间加一条连线。 （2）抹线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线。 （3）旋转：以树的根结点为轴心，将整棵树顺时针旋转45，使之成为二叉树。,返回到本节目录,【例5.3】将图5-15（a）所示的树转换成二叉树。,转换过程如图5-15(b)、(c)、(d)所示。,（a）原始树 （b）相邻兄弟之间加连线（虚线）,（c）删除与双亲结点的连线 (d)转换之后的二叉树 图5-15 一棵树转换成二叉树的过程,返回到本节目录,2森林转换为二叉树,将森林转换为二叉树的过程如下： （1）将森林中的每一棵树转换成相应的二叉树。 （2）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树作为前一棵二叉树根结点的右子树，直到把最后一棵二叉树作为其前一棵二叉树的右子树为止。此时所得到的二叉树就是由森林转换得到的二叉树。,返回到本节目录,【例5.4】将图5-16（a）所示的森林转换成二叉树。,解：转换的过程如图5-16（b）5-16（e）所示。,（a）森林 （b）相邻兄弟加连线（虚线）,（c）删除与双亲结点的连线 （d）每棵树转换成二叉树,返回到本节目录,【例5.4】,（e）所有的二叉树连接成一棵二叉树 图5-16 森林转换成二叉树的过程,返回到本节目录,5.4.2 二叉树还原为树、森林,1二叉树还原为树 二叉树还原为树的过程如下： （1）加线：如果某结点的左孩子有右子树，在该结点和其左孩子的右子树的右分支上各结点间加线。 （2）抹线：抹掉各结点的右子树的右分支取上的连线。 （3）旋转整理得到树。,返回到本节目录,5.4.2 二叉树还原为树、森林,2二叉树还原为森林 二叉树还原为森林的过程如下： （1）连线：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用连线连起来。 （2）抹线：删除原二叉树中原来双亲结点与右孩子结点的连线。 （3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。,返回到本节目录,5.5 哈夫曼树,5.5.1相关概念和哈夫曼树的定义 5.5.2 哈夫曼树的构造方法 5.5.3 哈夫曼编码,返回到总目录,5.5.1相关概念和哈夫曼树的定义,1路径 树中一个结点与另一个结点之间的分支构成这两个结点之间的路径。树中不是每对结点之间都有路径，如兄弟结点之间就无路径，而从根结点到树中任一结点都存在一条路径。 2路径长度 树中路径上的分支数目。 3树的路径长度 根结点到树中每个结点的路径长度之和。 4结点的权值 所谓权值是人们根据需要为每个叶子结点赋予的一个数值。,返回到本节目录,5结点的带权路径长度 是指从树根到该结点之间的路径长度与结点的权值的乘积。 6树的带权路径长度 树中所有叶子结点的权值乘以该结点的路径长度之和。用公式可以表示为： 其中，wk为第k个叶子结点的权值， lk 是从根结点到第k个叶子结点的路径长度。 7哈夫曼树 哈夫曼树又称为最优二叉树。它是n个带权值的叶子结点所构成的所有二叉树中带权路径长度WPL最小的二叉树。,返回到本节目录,求不同二叉树的WPL,如图5-19（a）、（b）、（c）所示的三棵二叉树，它们的带权路径长度分别为： （a）WPL=22+32+42+62=30 （b）WPL=23+33+42+61=29 （c）WPL=43+63+32+21=38,（a） （b） （c） 图5-19 相同叶子结点所构成的不同带权路径长度的二叉树,返回到本节目录,5.5.2 哈夫曼树的构造方法,下面介绍哈夫曼树的构造方法，步骤如下： （1）将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点； （2）在森林中选取两棵树根结点的权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点的权值为原来两棵树根结点的权值之和； （3）在森林中，将上面选择的这两棵根结点的权值最小的二叉树从森林中删除，并将最新构造的二叉树加入到森林中； （4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。,返回到本节目录,【例5.7】假设有一组权值2,3,7,8,12,9,6,19，下面我们将利用这组权值演示构造哈夫曼树的过程。 解：第一步：以这8个权值作为根结点的权值构造具有8棵树的森林。,第二步：从中选择两个根的权值最小的树2、3作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树5添加进去。,返回到本节目录,第三步：重复第二步过程，直到森林中只有一棵树为止 选择5、6，将11放回。,选择7、8，将15放回。,返回到本节目录,选择9、11，将20放回,选择12、15，将27放回。,返回到本节目录,选择19、20，将39放回。,选择27、39，最后森林中只有一棵树，结束操作，这棵树就是哈夫曼树。,返回到本节目录,为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下： typedef struct char data; /*结点值*/ int weight; /*权值*/ int parent; /*双亲结点下标*/ int lchild; /*左孩子结点下标*/ int rchild; /*右孩子结点下标*/ HTCode; /*哈夫曼树结点类型*/,返回到本节目录,用ht数组存放哈夫曼树，对于具有n个叶子结点的哈夫曼树，总共有2n-1个结点。其算法思路是：n个叶子结点只有data和weight域值，先将所有2n-1个结点的parent、lchild和rchild域置为-1。处理每个非叶子结点hti（存放在htnht2n-2中）：从ht0hti-2中找出根结点（即其parent域为-1）最小的两个结点htlnode和htrnode，将它们作为hti的左右子树，htlnode和htrnode双亲结点置为hti，并且hti.weight= htlnode.weight+htrnode.weight。如此这样直到所有的n-1个非叶子结点处理完毕。构造哈夫曼树的算法如算法5.7。,返回到本节目录,算法5.7 void CreateHT(HTCode ht,int n) int i,j,k,lnode,rnode; int min1,min2; for(i=0;i2*n-1;i+) /*将双亲、左、右孩子域置初值-1*/ hti.parent=hti.lchild=hti.rchild=-1; for(i=n;i2*n-1;i+) min1=min2=32767; /*两个最小值置初值为系统最大值*/ lnode=rnode=-1;,返回到本节目录,for(k=0;khtk.weight) min1=htk.weight; /*找出最小的权值*/ lnode=k; /*最小权值的结点下标值*/ for(k=0;khtk.weight /*次最小权值的结点下标值*/ ,返回到本节目录,htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; ,返回到本节目录,5.5.3 哈夫曼编码,1什么是哈夫编码？ 在进行快速远距离的通信时，经常需要将传送的文字转换成由二进制字符0，1组成的二进制代码，称之为编码。 如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。,返回到本节目录,5.5.3 哈夫曼编码,2生成哈夫曼编码的方法 要设计长短不同的编码，首先要做到不同字符的编码不会混淆，即任一个字符的编码都不是另一个字符的编码的前缀（即不是另一个字符编码的开头一部分），满足这个条件的编码叫做前缀编码。即前缀编码是指所编码的字符可以通过前缀唯一地正确识别并译出。利用哈夫曼树就可以方便的设计。,返回到本节目录,2生成哈夫曼编码的方法,（1）构造哈夫曼树 设需要编码的字符集合为d1，d2，dn，它们在电文中出现的次数集合为w1，w2，wn，以d1，d2，dn作为叶子结点，w1，w2，wn作为它们的权值，构造一棵哈夫曼树。 （2）在哈夫曼树上求叶结点的编码。 规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码。,返回到本节目录,【例5.8】设有A，B，C，D，E，F 6个字符，其出现的频度分别为0.06、0.02、0.04、0.03、0.07、0.12，试设计它们的哈夫曼编码。 解：将所有频度全部乘以100，得到各字符的权值6，2，4，3，7，12，根据这组权值构造的哈夫曼树如图5-21所示。并设哈夫曼树的每个左分支为0，右分支为1进行编码.,返回到本节目录,则得到各个字符的哈夫曼编码为： A：00 B：1010 C：100 D：1011 E：01 F：11,图5-21 哈夫曼编码树,返回到本节目录,3.哈夫曼编码的算法实现,（1）设计哈夫曼编码的数据类型如下： typedef struct char cdN; /*存放当前结点的哈夫曼编码*/ int start; /*start指向cd数组中的哈夫曼编码最开始字符*/ HCode; /*哈夫曼编码存放类型*/,返回到本节目录,3.哈夫曼编码的算法实现,（2）生成哈夫曼编码的算法 由于哈夫曼树中的每个叶子结点的哈夫曼编码长度不同，为此采用HCode类型变量的cdstartcdn存放当前结点的哈夫曼编码。只需对叶子结点求哈夫曼编码。对于当前叶子结点hti，先将对应的哈夫曼编码和hcdi的start域置初值n，找其双亲结点htf，若当前结点是双亲结点的左孩子，则在hcdi的cd数组中添加1，将start域减1。再对双亲结点进行同样的操作，如此直到无双亲结点即到达树根结点，最后让start指向哈夫曼编码最开始字符。具体算法如算法5.8所示。,返回到本节目录,算法5.8 void CreateHCode(HTCode ht,HCode hcd,int n) int i,f,c; HCode hc; for(i=0;in;i+) hc.start=n; c=i; f=hti.parent; while(f!=-1) if(htf.lchild=c) hc.cdhc.start-=0; else hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; hcdi=hc; ,返回到本节目录,（3）为了显示哈夫曼编码，设计输出函数如算法5.9所示。 算法5.9 void DispHCode(HTCode ht,HCode hcd,int n) int i,k; int sum=0,m=0; int j; printf(“n各字符的哈夫曼编码如下:n“); for(i=0;in;i+) j=0; printf(“n字符%c的哈夫曼编码为:“,hti.data); for(k=hcdi.start;k=n;k+) printf(“%c“,hcdi.cdk); j+; m+=hti.weight; sum+=hti.weight*j; printf(“n“); ,返回到本节目录,（4）为了使用以上各函数（包括生成哈夫曼树函数CreateHT()），设计主函数如下： #include “stdio.h“ /* getchar()函数需用此头文件*/ #define N 100 /*最大字符个数*/ main() HTCode htN; HCode hcdN; int i,n; clrscr(); printf(“n请输入电文的字符个数(0-50):“); scanf(“%d“,返回到本节目录,for(i=0;in;i+) printf(“第%d个字符为:“,i+1); getchar(); scanf(“%c“, ,返回到本节目录,（5）程序执行一次的结果如下：（带下划线文字为输入内容，表示回车）。,请输入电文的字符个数:5 请输入每个电文字符: 第1个字符为:a 第2个字符为:b 第3个字符为:c 第4个字符为:d 第5个字符为:e 请输入每个字符的使用频率(权值为正整数): 第1个字符的频率为:8 第2个字符的频率为:2 第3个字符的频率为:14 第4个字符的频率为:6 第5个字符的频率为:5 各字符的哈夫曼编码如下: 字符a的哈夫曼编码为:10 字符b的哈夫曼编码为:1110 字符c的哈夫曼编码为:0 字符d的哈夫曼编码为:110 字符e的哈夫曼编码为:1111,返回到本节目录,5.6 本章小结,本章中主要介绍下列内容： （1）树的逻辑定义基本术语，树的三种存储结构：双亲表示法，孩子表示法和孩子兄弟表示法。 （2）二叉树的逻辑定义、存储结构，二叉树的常用性质。二叉树的基本操作算法。二叉树的三种遍历方式：先（根）序遍历、中（根）序遍历、后（根）序遍历三种。介绍了已知遍历序列，恢复二叉树的方法。 （3）介绍树和二叉树的转换，森林与二叉树之间的转换。 （4）最后介绍了哈夫曼树的定义与建立方法，及哈夫曼编码。,返回到总目录,