《数据结构用C语言描述》第六章.j.ppt

《《数据结构用C语言描述》第六章.j.ppt》由会员分享，可在线阅读，更多相关《《数据结构用C语言描述》第六章.j.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 树和二叉树树和二叉树树的概念和基本术语二叉树 二叉树遍历二叉树的计数树与森林哈夫曼树 树的概念和基本术语树的概念和基本术语树的定义树的定义 树是由树是由 n(n 0)个结点的有限集合。如个结点的有限集合。如果果 n=0，称为空树；如果，称为空树；如果 n 0，则，则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的的结点，它只有直接后继，但没有直接前驱；结点，它只有直接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为除根以外的其它结点划分为 m(m 0)个互不相交的有限集个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称其中每个集

2、合本身又是一棵树，并且称为根的子树为根的子树(SubTree)。ACGBDEFKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树树的基本术语树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点结点的度结点的度叶结点叶结点分支结点分支结点子女子女双亲双亲兄弟兄弟祖先祖先子孙子孙结点层次结点层次树的深树的深度度树的

3、度树的度森林森林二叉树二叉树(Binary Tree)定义定义五种形态五种形态一棵二叉树是结点的一个有限集合，一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不上两棵分别称为左子树和右子树的、互不相交的二叉树组成。相交的二叉树组成。LLRR特点特点每个结点至多只有两棵子树（二叉树中每个结点至多只有两棵子树（二叉树中不存在度大于不存在度大于2的结点）的结点）性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i 1个结点。个结点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有

4、根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层层上至多有上至多有2 j-1 个结点。个结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在，故在第第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结层上的最大结点数的点数的2倍，即倍，即2*2i 2=2 i-1。性质性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k-1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二

5、叉树的的二叉树的最大结点数为最大结点数为 20+21+2 k-1=2 k-1性质性质3 对任何一棵二叉树对任何一棵二叉树T,如果其叶如果其叶结点数为结点数为 n0,度为度为2的结点数为的结点数为 n2,则则n0n21.证明：若度为证明：若度为1的结点有的结点有 n1 个，总结点个个，总结点个数为数为 n，总边数为，总边数为 e，则根据二叉树的定，则根据二叉树的定义，义，n=n0+n1+n2 e=2n2+n1=n-1因此，有因此，有 2n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1 定义定义1 满二叉树满二叉树(Full Binary Tree)一棵深度为一棵深度为k且有且有2

6、 k-1个结点的二叉树称为个结点的二叉树称为满二叉树。满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二叉树非完全二叉树定义定义2 完全二叉树完全二叉树(Complete Binary Tree)若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第 h 层外，其它各层层外，其它各层(0 h-1)的结点数都达到的结点数都达到最大个数，第最大个数，第 h 层层从右向左从右向左连续缺若干结点，连续缺若干结点，这就是完全二叉树。这就是完全二叉树。621754389 10 11 12

7、完全二叉树完全二叉树性质性质4 具有具有 n(n 0)个结点的完全二叉树个结点的完全二叉树的深度为的深度为 log2(n)1 证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h，则根据性，则根据性质质2和完全二叉树的定义有和完全二叉树的定义有2h1-1 n 2h-1或或 2h1 n 2h取对数取对数 h1 0,则则 i 的双亲为的双亲为 i/2 n 若若2*i =n,则则 i 的左子女为的左子女为 2*i，若若2*i+1-lchild);printf(“t%cn”,t-data);InOrder(t-rchild);中序遍历二叉树的递归算法中序遍历二叉树的递归算法前序遍历二叉树算法的定义

8、：前序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则访问根结点访问根结点(D)；前序遍历左子树前序遍历左子树(L)；前序遍历右子树前序遍历右子树(R)。遍历结果遍历结果-+a*b-c d/e f前序遍历前序遍历(Preorder Traversal)-/+*abcdef前序遍历二叉树的递归算法前序遍历二叉树的递归算法void PreOrder(bitree *t)if(t!=NULL)printf(“t%cn”,t-data);PreOrder(t-lchild);PreOrder(t-rchild);后序遍历二叉树算法的定义：后序遍历二叉树算法的定义：若二叉树

9、为空，则空操作；若二叉树为空，则空操作；否则否则后序遍历左子树后序遍历左子树(L)；后序遍历右子树后序遍历右子树(R)；访问根结点访问根结点(D)。遍历结果遍历结果 a b c d-*+e f/-后序遍历后序遍历(Postorder Traversal)-/+*abcdef后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：void PostOrder(bitree*t)if(t!=NULL)PostOrder(t-lchild);PostOrder(t-rchild);printf(“t%cn”,t-data);int Count(bitree*T)if(T=NULL)return 0;el

10、se return 1+Count(T-lchild)+Count(T-rchild);1.计算二叉树结点个数计算二叉树结点个数(递归算法递归算法)int Leaf_Count(Bitree*T)/求二叉树中叶子结点的数目求二叉树中叶子结点的数目 if(!T)return 0;/空树没有叶子空树没有叶子 else if(!T-lchild&!T-rchild)return 1;/叶子结点叶子结点else return Leaf_Count(T.lchild)+Leaf_Count(T.rchild);/左子树的叶子数加上右子树的叶子数左子树的叶子数加上右子树的叶子数2.求二叉树中叶子结点的个数

11、求二叉树中叶子结点的个数int Height(bitree*T)int m,n;if(T=NULL)return -1;else m=Height(T-lchild);n=Height(T-rchild );return(m n)?m+1:n+1;3.求二叉树高度求二叉树高度(递归算法递归算法)4.复制二叉树复制二叉树(递归算法递归算法)int Copy(bitree*T)if(T=NULL)return-1;bitree*temp;Temp-data=T-data;Temp-lchild=Copy(T-lchild);Temp-rchild=Copy(T-rchild);return tem

12、p;5.判断二叉树等价判断二叉树等价(递归算法递归算法)int Equal(bitree*a,bitree*b)if(a=NULL&b=NULL)return 1;if(a!=NULL&b!=NULL&a-data=b-data&equal(a-lchild,b-lchild)&equal(a-rchild,b-rchild)return 1;else return 0;/a和和b的子树不等同的子树不等同中序遍历二叉树中序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现baabcdeadaaa b入栈入栈b退栈退栈访问访问d入栈入栈d退栈退栈访问访问e 退栈退栈 访问访问ecc栈空栈空 a退

13、栈退栈访问访问c e 入栈入栈c 退栈退栈 访问访问 void InOrder(bitree*T)stack *S;SETNULL(S);/递归工作栈递归工作栈 bitree*p=T;/初始化初始化 while(p!=NULL|!Empty(S)if(p!=NULL)Push(S,p);p=p-lchild;if(!Empty(S)/栈非空栈非空 Pop(S,p);/退栈退栈 printf(“%cn”,p-data);/访问根访问根 p=p-rchild;/if /while return ok;abcde前序遍历二叉树前序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现acabcdedcc

14、访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 结束结束void PreOrder(bitree *T)stack*S;SETNULL(S);/递归工作栈递归工作栈 bitree*p=T;Push(S,NULL);while(p!=NULL)printf(“%cn”,p-data);if(p-rchild!=NULL)Push(S,p-rchild);if (p-lchild!=NULL)p=p-lchild;/进左子树进左子树 else Pop(S,p);abcdev后序遍历二叉树后序

15、遍历二叉树(非递归算法非递归算法)用栈实现用栈实现后序遍历时使用的栈的结点定义后序遍历时使用的栈的结点定义typedef struct bitree*ptr;/结点指针结点指针 enum tag L,R;/该结点退栈标记该结点退栈标记 StackNode;根结点的根结点的 tag=L，表示从左子树退出，表示从左子树退出,访问右子树。访问右子树。tag=R,表示从右子树退出表示从右子树退出,访问根。访问根。ptr tagL,R vvoid PostOrder(BinTree T)stack S;InitStack(&S);StackNode w;bitree*p=T;do while(p!=NU

16、LL)/向左子树走向左子树走 w.ptr=p;w.tag=L;Push(&S,w);p=p-lchild;int continue=1;/继续循环标记继续循环标记 while(continue&!StackEmpty(&S)Pop(&S,w);p=w.ptr;switch(w.tag)/判断栈顶判断栈顶tag标记标记 case L:w.tag=R;Push(&S,w);continue=0;p=p-rchild;break;case R:cout-data endl;while(p!=NULL|!StackEmpty(&S);cout-lchild;p-lchild=p-rchild;p-rc

17、hild=temp;unknown(p-lchild);unknown(p-rchild);void unknown(bitree*T)bitree*p=T,*temp;while(p!=NULL)temp=p-lchild;p-lchild=p-rchild;p-rchild=temp;unknown(p-lchild);p=p-rchild;不用栈消去递归算法中的第二个递归语句不用栈消去递归算法中的第二个递归语句 使用栈消去递归算法中的两个递归语句使用栈消去递归算法中的两个递归语句void unknown(bitree*T)bitree*p,*temp;stack *S;SETNULL(S

18、);if(T!=NULL)push(S,T);while(!Empty(S)Pop(S,p);/栈中退出一个结点栈中退出一个结点 temp=p-lchild;/交换子女交换子女 p-lchild=p-rchild;p-rchild=temp;if(p-rchild!=NULL)push(S,p-rchild);if(p-lchild!=NULL)push(S,p-lchild);ltag=0,lchild为为左子女指针左子女指针ltag=1,lchild为为前驱线索前驱线索rtag=0,rchild为为右子女指针右子女指针rtag=1,rchild为为后继指针后继指针lchildlchildr

19、childrchilddatadataltagrtagv线索二叉树线索二叉树(Threaded Binary Tree)结点结构结点结构 下面给出线索链表的形式说明下面给出线索链表的形式说明：typedef int datatype;typedef struct node int ltag,rtag;datatype data;struct node *lchild,*rchild;bithptr;bithptr *pre;通过中序遍历建立中序线索化二叉树通过中序遍历建立中序线索化二叉树bithptr *pre=null;INTHREAD(bithptr*p)if(p!=NULL)INTHRE

20、AD(p-lchild);/左子树线索左子树线索化化 if(p-lchild=NULL)p-lchild=pre;p-ltag=1;/建立当前结点的前驱线索建立当前结点的前驱线索 if(pre!=NULL&pre-rchild=NULL)pre-rchild=p;pre-rtag=1;/建立前驱结点的后继线索建立前驱结点的后继线索pre=p;/前驱跟上当前指针前驱跟上当前指针INTHREAD(p-rchild);/递归递归,右子树线索化右子树线索化 q树的存储结构树的存储结构双亲表示：以一组连续空间存储树的结点，双亲表示：以一组连续空间存储树的结点，同时在同时在结点中附设一个指针，存放双亲结点

21、结点中附设一个指针，存放双亲结点在链表中的位置。在链表中的位置。树与森林树与森林ABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 30 1 2 3 4 5 6用双亲表示实现的树定义用双亲表示实现的树定义#define MaxSize /最大结点个数最大结点个数typedef char datatype;/结点数据结点数据typedef struct /树结点定义树结点定义 datatype data;int parent;TreeNode;typedef TreeNode TreeMaxSize;/树树ABCDEFG左子女左子女-右兄弟表示法右兄弟表示法第一

22、种解决方案第一种解决方案 等数量的链域等数量的链域 data child1child2child3childdABCDEFG 空链域n(k-1)+1个结点结构结点结构 datafirstChildnextSiblingABCDEFG空链域n+1个第二种解决方案第二种解决方案 树的左子女树的左子女-右兄弟表示右兄弟表示（二叉链表表示）（二叉链表表示）BCDGFE A typedef char datatype;typedef struct node datatype data;struct node*firstChild,*nextSibling;TreeNode;typedef TreeNod

23、e*Tree;用左子女用左子女-右兄弟表示实现的树定义右兄弟表示实现的树定义(1)树转化成二叉树的简单方法树转化成二叉树的简单方法在同胞兄弟之间加连线；在同胞兄弟之间加连线；在同胞兄弟之间加连线；在同胞兄弟之间加连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；顺时针旋转顺时针旋转顺时针旋转顺时针旋转4545度。度。度。度。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。森林转化成二叉

24、树森林转化成二叉树将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；将森林中已经转换成的二叉树的各个根视为兄弟，将森林中已经转换成的二叉树的各个根视为兄弟，将森林中已经转换成的二叉树的各个根视为兄弟，将森林中已经转换成的二叉树的各个根视为兄弟，各兄弟之间自第一棵树根到最后一棵树根之间加连各兄弟之间自第一棵树根到最后一棵树根之间加连各兄弟之间自第一棵树根到最后一棵树根之间加连各兄弟之间自第一棵树根到最后一棵树根之间加连线；线；线；线；以第一棵树的根为轴，顺时针旋转以第一棵树的根为轴，顺时针旋转以第一棵树

25、的根为轴，顺时针旋转以第一棵树的根为轴，顺时针旋转4545度度度度。T1 T2 T3T1 T2 T3AFHB C DGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示q森林与二叉树的转换森林与二叉树的转换树的二叉树表示树的二叉树表示:q树的遍树的遍历历n深度优先遍历深度优先遍历u 先根次序遍历先根次序遍历u 后根次序遍历后根次序遍历ABCDE FGABCEDGF深度优先遍历深度优先遍历n当树非空时当树非空时u 访问根结点访问根结点u 依次先根遍历根的各棵依次先根遍历根的各棵 子树子树n树先根遍历树先根遍历 ABEFCDGn对应二叉树前序遍历对

26、应二叉树前序遍历 ABEFCDGn树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同表示的前序遍历结果相同n树的先根遍历可以借助对应二叉树的前序遍历树的先根遍历可以借助对应二叉树的前序遍历算法实现算法实现ABCEDGF树的树的先根次序先根次序遍遍历历树的树的后根次序后根次序遍历遍历:n当树非空时当树非空时u依次后根遍历根的各棵依次后根遍历根的各棵 子树子树u访问根结点访问根结点n树后根遍历树后根遍历 EFBCGDAn对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAn树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同表示的中

27、序遍历结果相同n树的后根遍历可以借助对应二叉树的中序遍历算树的后根遍历可以借助对应二叉树的中序遍历算法实现法实现ABCEDGF二叉树的计数二叉树的计数 由二叉树的前序序列和中序序列可唯一由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。地确定一棵二叉树。例例,前序序列前序序列 ABHFDECKG 和中序序和中序序列列 HBDFAEKCG,构造二叉树过程如下：构造二叉树过程如下：HBDFEKCGAEKCGABHDFKCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG 如果前序序列固定不变，给出不同的中序如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。序列，可得

28、到不同的二叉树。612345789612375849 固定前序排列固定前序排列,选择所有可能的中序排列选择所有可能的中序排列,可以构造多少种不同的二叉树？可以构造多少种不同的二叉树？例如例如,有有 3 个数据个数据 1,2,3，可得，可得 5 种不种不同的二叉树。它们的前序排列均为同的二叉树。它们的前序排列均为 123，中，中序序列可能是序序列可能是 321，231，213，132，123.123123123123123 具有具有n个结点不同形态的树的数目和具有个结点不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同。个结点互不相似的二叉树的数目相同。有有0个个,1个个,2个个,3

29、个结点的不同二叉树如个结点的不同二叉树如下下b0=1b1=1b2=2b3=5 b4=14v计算具有计算具有 n 个结点的不同二叉树的棵数个结点的不同二叉树的棵数最终结果：最终结果：bibn-i-11哈夫曼树哈夫曼树(Huffman Tree)路径长度路径长度(Path Length)两个结点之间的路径长度两个结点之间的路径长度 PL 是连接两结是连接两结点的路径上的分支数。点的路径上的分支数。树的外部路径长度是各叶结点树的外部路径长度是各叶结点(外结点外结点)到根结点的路径长度之和到根结点的路径长度之和 EPL。树的内部路径长度是各非叶结点树的内部路径长度是各非叶结点(内结点内结点)到根结点的

30、路径长度之和到根结点的路径长度之和 IPL。树的路径长度树的路径长度 PL=EPL+IPL123456782345678树的外部路径长度树的外部路径长度EPL=3*1+2*3=9树的外部路径长度树的外部路径长度EPL=1*1+2*1+3*1+4*1=101带权路径长度带权路径长度(Weighted Path Length,WPL)二叉树的带权二叉树的带权(外部外部)路径长度是树的各路径长度是树的各叶结点所带的权值叶结点所带的权值 wi 与该结点到根的路径长与该结点到根的路径长度度 li 的乘积的和。的乘积的和。WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*

31、2+2*3+7*2=36 7*3=46 4*3=35 222444555777带权带权(外部外部)路径路径长度达到最小长度达到最小哈夫曼树哈夫曼树n带权路径长度达到最小的二叉树即为哈夫带权路径长度达到最小的二叉树即为哈夫曼树。曼树。n在哈夫曼树中，权值大的结点离根最近在哈夫曼树中，权值大的结点离根最近。(1)由给定的由给定的 n 个权值个权值 w0,w1,w2,wn-1，构造具有，构造具有 n 棵扩充二叉树的森林棵扩充二叉树的森林 F=T0,T1,T2,Tn-1，其中每棵扩充二叉树，其中每棵扩充二叉树 Ti 只只有一有一 个带权值个带权值 wi 的根结点的根结点,其左、右子树均为其左、右子树均

32、为空。空。哈夫曼哈夫曼算法算法 (2)重复以下步骤重复以下步骤,直到直到 F 中仅剩下一棵中仅剩下一棵树为止：树为止：在在 F 中选取两棵根结点的权值最小的中选取两棵根结点的权值最小的扩充二叉树扩充二叉树,做为左、右子树构造一棵新做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。其左、右子树上根结点的权值之和。在在 F 中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入 F。F:7 5 2 4F:7 5 6F:7 11 7524初始合并2 475246F:18 1175246合并5 65合并

33、7 1127461118举例哈夫曼树的构造过程举例哈夫曼树的构造过程5274Weight parent lchild rchild7 -1 -1 -15 -1 -1 -12 -1 -1 -14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456上例存储结构上例存储结构初初 态态52746Weight parent lchild rchild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -10123456p1p24423i过过 程程5274611Weight pare

34、nt lchild rchild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -10123456p1p25514i5274611Weight parent lchild rchild 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1 -1 -10123456p1p26605i18终终 态态 int n=20;/叶结点数叶结点数 int m=2*n-1;/结点数结点数 typedef struct float weight;int

35、 parent,lchild,rchild;hufmtree;hufmtreem;哈夫曼树的定义哈夫曼树的定义建立哈夫曼树的算法建立哈夫曼树的算法void CreateHuffmanTree(HuffmanTree T,float fr )for(int i=0;i n;i+)Ti.weight=fri;for(i=0;i m;i+)Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1;for(i=n;i m;i+)int min1=min2=MaxNum;int pos1,pos2;for(int j=0;j i;j+)if(Tj.parent=-1)if(Tj.we

36、ight min1)pos2=pos1;min2=min1;pos1=j;min1=Tj.weight;else if(Tj.weight min2)pos2=j;min2=Tj.weight;Ti.lchild=pos1;Ti.rchild=pos2;Ti.weight=Tpos1.weight+Tpos2.weight;Tpos1.parent=Tpos2.parent=i;最佳判定树最佳判定树考试成绩分布表考试成绩分布表 判定树判定树不及格不及格不及格不及格及格及格及格及格中中中中良良良良优优优优60?70?80?90?0.100.150.250.350.15 WPL=0.10*1+0.

37、15*2+0.25*3+0.35*4+0.15*4 =3.15 最佳判定树最佳判定树不及格不及格不及格不及格及格及格及格及格中中中中良良良良优优优优60?70?80?90?0.100.150.250.350.15 WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 =0.3+0.45+0.5+0.7+0.3=2.25 哈夫曼编码哈夫曼编码主要用途是实现数据压缩。主要用途是实现数据压缩。设给出一段报文：设给出一段报文：CAST CAST SAT AT A TASA 字符集合是字符集合是 C,A,S,T，各个字符出现，各个字符出现的频度的频度(次数次数)是是 W 2,7,

38、4,5。若给每个字符以等长编码若给每个字符以等长编码 A:00 T:10 C:01 S:11则总编码长度为则总编码长度为(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。长编码，可望减少总编码长度。各字符出现概率为各字符出现概率为 2/18,7/18,4/18,5/18,化整为化整为 2,7,4,5。以它们为各叶结点上的。以它们为各叶结点上的权值权值,建立哈夫曼树。建立哈夫曼树。左分支赋左分支赋 0，右分支赋，右分支赋 1，得哈夫曼编码，得哈夫曼编码(变长编码变长编码)。7254010011A AC CT TS S A:0 T:10 C:110 S:111它的总它的总编码长度：编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。比等长编码的情形要短。总编码长度正好等于哈夫总编码长度正好等于哈夫曼树的带权路径长度曼树的带权路径长度WPL。哈夫曼编码是一种哈夫曼编码是一种无前缀无前缀编码。解码时不会混淆。编码。解码时不会混淆。哈夫曼编码树哈夫曼编码树0001112457