大学教程(零起点)数据结构- 树和二叉树

复习前节1、数据结构的基本概念2、顺序表、链表3、顺序栈、链栈4、顺序队、链队5、顺序串、链串6、数组和广义表线性表线性表的推广树的推广1第五章树和二叉树5.1树的概念和术语5.2二叉树5.3二叉树的运算5.4线索二叉树5.5树和森林5.6哈夫曼树及其应用2本章项目：电文编码3文字电文编码电波译码摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由美国人艾尔菲德·维尔发明（1835年）。4网络信息传输：文字数字编码电信号电文编码发送者数字编码文字电文编码接收者你好0101010101你好核心问题：电文如何编码称为01串？？51、树的概念2、树的专业术语3、二叉树的概念4、哈夫曼树和哈夫曼编码6789自然中的树抽象的树知识点1：树的概念10旋转后11适当进行调整ABCDEFGHI12数据结构中树的形态，具有分层特点ABCDEFGHI13某姓氏族谱14ABCDEFGHIJKLMNOPQRSTUVWXYZ……..对树中的结点给定一个符号名称，具有一对多的特点15树描述的是一种层次结构，是一种一对多的逻辑关系FGIJABCEDH16树(Tree)是n(n>=0)个结点的有限集T。n=0时称为空树。对于非空树有且仅有一个称为根(ROOT)的结点；n>1其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树知识点1：树的定义FGIJABCEDH根根17树的其他表示形式ABCDEFHGM18结点：数据元素的内容及其指向其子树根的分支结点的度（Degree）：结点拥有的子树的数目。树的度：一棵树内各结点的度的最大值；知识点3：树的基本术语ABCDEFHGMA、B、C、D、E、F、G、H、M均称为结点A结点的度为2C结点的度为3M结点的度为0树的度为319叶子（终端结点Leaf），非终端结点：度为0的结点称为叶子结点；度不为0的结点称为非终端结点。ABCDEFHGM知识点3：树的基本术语20孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；双亲在同一层的结点互为堂兄弟。ABCDEFHGMA是B、C的双亲B、C是A的孩子B、C是兄弟关系E、F是堂兄弟关系21路径：若树中存在一个序列k1，k2…kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数ABCDEFHGM序列：ABDME序列：ABDM序列：ACF是路径非路径是路径22子孙，祖先：以某结点为根的子树中的所有结点都被称为是该结点的子孙。从根结点到该结点路径上的所有结点称为该结点的祖先。ABCDEFHGM23结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的高度（深度）：树中所有结点层次的最大值ABCDEFHGM24森林：多棵互不相交的树的集合构成森林BCDEFHGM三棵树构成的森林IJA25结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙路径ABCDEFHGM26ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点G的祖先是结点A，C结点D的子孙为H,I,J,M27知识点3：二叉树的概念二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树ABCDEFHM28特征：每个结点最多只有两棵子树子树有左右之分，次序不能任意颠倒，只有一棵子树时也必须分清是左子树还是右子树ABCACB29二叉树的五种基本形态AAAA(a)(b)(c)(d)(e)(a)空二叉树(b)单结点二叉树(c)右子树为空(d)左子树为空(e)左、右子树非空二叉树的五种基本形态30性质1.非空二叉树的第i层上至多有2i-1个结点（i1）证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1个结点

当i=k+1时，最多的结点个数：

2k-1*2=2k-1+1=2k=2(

k+1)-1二叉树的性质12345678910111213141531性质2.深度为k的二叉树至多有2k-1个结点(k1)

证明：二叉树的结点个数为：

1+2+…+2k-1=2k-112345678910111213141532性质3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为T中度为1的结点数，则总结点数：

n=n0+n1+n2(1)

另：根据各个结点的前驱和后继情况度数为1的结点表示有一个孩子结点度数为2的结点表示有两个孩子节点所以树中孩子结点总数为

n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故

n0=n2+1;33考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。满二叉树(FullBinaryTree)深度为k且有2k-1个结点的二叉树12345678910111213141534完全二叉树若一颗深度为k的二叉树，其k-1层是一颗满二叉树，而最下面一层，即第k层上的结点都集中在该层最左边的若干位置上，则称作完全二叉树。abcdefghij35894101151213614157213894101152112673(a)满二叉树(b)完全二叉树1362455674213(c)非完全二叉树图6-4特殊形态的二叉树361.满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。(√)2.满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。

(√)判断题37性质4.具有n个结点的完全二叉树的深度:k=log2(n)+1证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即

2k-1-1<n≤2k-1进一步可推导出

2k-1≤n<2k两边取对数后，有

k-1≤log2(n)<k进一步可推导出

log2(n)<k≤log2(n)+1因为k是整数，所以有k＝log2(n)+138（a）如果i=1,此结点为根结点，无双亲；若i>1,则其双亲结点是i/2。（b）如果2i>n,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。（c）如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1。性质5.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,…,n,则对任一结点i（1in）有abcdefghij391.一棵树高为K的完全二叉树至少有（）个结点A.2k–1B.2k-1–1C.2k-1

D.2k习题答案：C相当于k-1层的满二叉树加一个结点K-1层满二叉树结点个数为：2k-1-1402.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。习题结点总个数n=2+3+4+x结点数为所有结点的度数之和加1n=2*1+3*2+4*3+x*0+1（根节点）故x=12答案：1241习题3.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2答案：B424、如果知道完全二叉树上有1001个结点，其叶子结点的个数为多少？

深度为9的节点数是511，深度为10的节点数是1023，该树为10层。最后一层节点是1001-511=490（均是叶子节点），最后一层490个节点对应的第9层得父节点有245个，第9层节点共有256个节点，所以第9层叶子节点有256-245=11个总的叶子节点数为490+11=501习题43习题5、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8445.2.3二叉树的存储结构顺序存储结构链式存储结构45abcdefghij二叉树的顺序存储结构整个二叉树可以按照从上到下，从左到右的顺序编号46将一棵二叉树按完全二叉树顺序存放到一维数组中abcdefghm123456789101112131415

0123456789101112131415abcdefghm47顺序存储结构举例ABCABCØØØØAØBØØØC48对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便;若为非完全二叉树,将会浪费大量存贮单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。49链式存储结构二叉链表三叉链表50二叉链表lchilddatarchildABDCEFADEBCFBinTree51二叉链表的定义struct

btnode

{//结点结构

datatypedata;

struct

btnode*lchild,*rchild;};结点结构:lchilddatarchild52ADEBCFBinTree问题：如何找到某结点的子树？如何找到某结点的双亲？53三叉链表lchilddatarchildparentADEBCFBinTree54三叉链表的定义struct

btnode

{//结点结构

datatypedata;

struct

btnode*lchild,*rchild}；结点结构:lchilddatarchildparent,*parent;;55链式存储的缺点；

若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用。565.3.1二叉树的生成建立二叉树的存储结构链式存储结构——二叉链表1、按广义表表示二叉树结构生成二叉链表的算法2、按完全二叉树的层次顺序依次输入结点信息建立二叉链表的算法5.3二叉树的运算571、按广义表表示二叉树结构生成二叉链表的算法（A（B（,D（E,F））,C））靠近左括号的结点是在左子树上，而逗号右边的结点是在右子树上。ACBDFE582、按完全二叉树的层次顺序依次输入结点信息建立二叉链表的算法首先对一般的二叉树添加若干个虚点，使其成为完全二叉树59605.3.2二叉树的遍历遍历一棵二叉树是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法“访问”的含义可以很广，如：输出结点的信息等61若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：AECBGL62若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：AECBGL63若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：AECBGL64先（根）序的遍历算法：voidPreorder(bitreptr

bt){//先序遍历二叉树

if(bt！=NULL){visit(bt);Preorder(bt->lchild);Preorder(bt->rchild);

}}AECBGL65中（根）序的遍历算法：voidInorder(bitreptr

bt){//中序遍历二叉树

if(bt！=NULL){

Inorder(bt->lchild);visit(bt);

Inorder(bt->rchild);

}}AECBGL66后（根）序的遍历算法：voidPostorder(bitreptr

bt){//后序遍历二叉树

if(bt！=NULL){

Postorder(bt->lchild);

Postorder(bt->rchild);visit(bt);

}}AECBGL67二叉树的遍历算法：AECBGLDLRLDR、LRD、DLR68ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A69习题

1.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是LRNB.NRLC.RLND.RNL答案：D70习题

2.假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，请确定一棵二叉树ABDGHCEFIGDHBAECIF前序中序71习题

3.试找出满足下列条件的二叉树1）先序序列与中序序列相同2）中序序列与后序序列相同3）先序序列与后序序列相同答案1）不含左子树的二叉树2）不含右子树的二叉树3）空二叉树或只含根结点的二叉树72习题

4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是()的二叉树

A．空或只有一个结点B.高度等于其结点数C．任一结点无左孩子D.任一结点无右孩子先序：根左右后序：左右根答案：B732、非递归遍历算法利用栈（1）、利用栈的非递归中序遍历74中序非递归算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)75pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)76ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)77ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)785.3.3二叉树的应用举例例5.2已知二叉树的前序和中序遍历序列（中序和后序遍历序列），确定二叉树。已知二叉树的前序和中序遍历序列在前序序列中寻找根到中序序列中分左右规律已知二叉树的中序和后序遍历序列在后序序列中寻找根到中序序列中分左右795.3.3二叉树的应用举例例5.3已知二叉树的链式存储结构，求二叉树的深度。例5.4以二叉链表为存储结构，试编写在二叉树中查找值为x的结点以及求x所在结点在树中层数的算法805.4线索二叉树81ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列82ADEBCFrootABDCEF缺点：空指针较多，找某个序列的前序后继不方便83指向某遍历序列中的“前驱”和“后继”的指针，称作“线索”包含“线索”的存储结构，称作“线索链表”与其相应的二叉树，称作“线索二叉树”利用链表中空的左指针指向遍历序列的前驱利用链表中空的右指针指向遍历序列的后继8485对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，标志二叉树中的左右指针指向的是前驱还是后继Tag值为1表示存的是线索值为0表示存的是孩子86Tag值为1表示存的是线索值为0表示存的是孩子中序线索87Tag值为1表示存的是线索值为0表示存的是孩子中序线索88typedef

struct

BiThrNod{

TElemTypedata;

struct

BiThrNode*lchild,*rchild;

PointerThr

LTag,RTag;}BiThrNode,*BiThrTree;线索链表的类型typedef

enum{Link,Thread}PointerThr;Link值为0:指针，Thread值为1:线索89二、线索链表的遍历算法:中序线索由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。90中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索树中结点的后继是哪个结点？左子树上处于”最左下”(没有左子树)的结点。若某节点无右子树，则其后继是右指针所指结点否则为对其右子树进行中序遍历时访问的第一个结点。91若某节点无右子树，则其后继是右指针所指结点ADEBCFroot925.5树和森林树的存储结构树和二叉树之间的转换森林和二叉树的转换树和森林的遍历93树的存储结构ABECDF双亲表示法

孩子链表表示法

孩子兄弟链表表示法

94双亲表示法树的双亲表示法主要描述的是结点的双亲关系顺序表示，存放顶点和双亲信息HDEFGBCA双亲表示法缺点：求结点的孩子时需要遍历整个结构01234567DataParent

A

-1

B

0

C

0

D

1

E

1

F

4

G

4

H

41234095孩子表示法来存储方法：将每个结点的孩子排列起来，形成一个带表头（装父亲结点）的线性表（n个结点要设立n个链表），再将n个表头用数组存放起来，这样就形成一个混合结构。HDEFGBCA孩子表示法

B

C^A

D

E^BC^D^

F

G

H^EF^G^H^0123456796HDEFGBCA带双亲的孩子表示法ParentData01234567ABCDEFGH-10011444

B

C^

D

E^

F

G

H^^^^^^带双亲的孩子表示法97用孩子兄弟表示法来存储方法：用二叉链表来存储树，但链表的两个指针域含义不同。firstchilddatanextsibling指向结点的第一个孩子指向结点的第一个兄弟HDEFGBCA孩子兄弟表示法AB^DC^^^EF^^GH^^^98请画出该树的孩子链表结构图请画出该树的孩子兄弟链表结构图双亲表示法结构图995.5.2树、森林与二叉树的转换1、树（森林）到二叉树转换—唯一的二叉树与之对应(1)加线：在各兄弟结点之间用虚线相连。(2)抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其它孩子之间的连线。(3)旋转：把虚线改为实线从水平方向向下旋转45℃，成右斜下方向。原树中实线成左斜下方向。这样就树的形状成呈现出一棵二叉树。100ABDCEGFHIMJNKL1、加线2、抹线1011、加线ABDCEGFHIMJNKL2、抹线3、旋转102ABDCEGFHIMJNKLKABDCEGFHIMJNL1035.5.2树、森林与二叉树的转换2、二叉树到树（森林）转换二叉树必须是没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。其实现过程：（１）加线：若某结点i是双亲结点的左孩子，则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点i的双亲结点用虚线连接。（２）抹线：把原二叉树中所有双亲结点与其右孩子的连线抹去。（３）进行整理：把虚线改为实线，把结点按层次排列。104ABCDEFGHIJKLABCDEFGHIJKLCDABCDEFGHIJKLC105DEFGHIJLABCKFILCABEGHJKD习题二叉树到森林的转换1065.5.3

树和森林的遍历1树的遍历

由树结构的定义可知，树的遍历有二种方法。⑴

先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如右图的树，先序遍历的次序是：ABCDEFGIJHK⑵

后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如右图的树，后序遍历的次序是：CDBFGIJHEKAABDCKGJIFHE树107说明：◆树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。◆树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。1082森林的遍历

设F={T1,T2,⋯,Tn}是森林，对F的遍历有二种方法。⑴先序遍历：按先序遍历树的方式依次遍历F中的每棵树。⑵中序遍历：按后序遍历树的方式依次遍历F中的每棵树。109习题设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是()。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右边兄弟C.在树T中，X一定是叶子结点D.在树T中，X一定有左边兄弟答案：D110中序遍历：BDCEAFHG

后序遍历：DECBHGFA111112113二叉树的存储结构顺序存储结构整个二叉树可以按照从上到下从左到右的顺序编号链式存储结构二叉链表三叉链表lchilddatarchildparentlchilddatarchild二叉树的遍历：前序遍历、中序遍历、后序遍历树的存储结构：双亲表示法

孩子链表表示法

孩子兄弟链表表示法

01234567DataParent

A

-1

B

0

C

0

D

1

E

1

F

4

G

4

H

4HDEFGBCA

B

C^A

D

E^BC^D^

F

G

H^EF^G^H^01234567AB^DC^^^EF^^G^114树、森林与二叉树的转换1、树（森林）到二叉树转换—唯一的二叉树与之对应(1)加线：在各兄弟结点之间用虚线相连。(2)抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其它孩子之间的连线。(3)旋转：2、二叉树到树（森林）转换(1)加线：若某结点i是双亲结点的左孩子，则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点i的双亲结点用虚线连接。(2)抹线：把原二叉树中所有双亲结点与其右孩子的连线抹去。(3)进行整理：1155.6哈夫曼树及其应用赫夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。1

基本概念①结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。②路径长度：结点路径上的分支数目称为路径长度。③树的路径长度：从树根到每一个结点的路径长度之和。116如图所示的树A到F：结点路径AEF；路径长度(即边的数目)2

；树的路径长度：31+52+23=19

ABDCKGJIFHE树117④结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。权(值)：各种开销、代价、频度等的抽象称呼。⑤

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做：其中：n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度。⑥

Huffman树：具有n个叶子结点(每个结点的权值为wi)的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树)

。118例有4个结点，权值分别为8，5，2，4，构造有4个叶子结点的二叉树abcd8524WPL=8*2+5*2+2*2+4*2=38dcab2485WPL=8*3+5*3+2*1+4*2=49abcd8524WPL=8*1+5*2+2*3+4*3=36119哈夫曼树的构造方法

(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。

(2)重复以下步骤,直到F中仅剩下一棵树为止：

①在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

②在F中删去这两棵二叉树。

③把新的二叉树加入F。1209例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树5627第一步：把每个权值看作只有一个结点的树1219例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树5267第二步：取权值最小的两棵树，合并成，新树的权值为两棵子树权值之和71229例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树5267第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树71239例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树5267713第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树1249例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树1259例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树1269例如:已知权值W={5,6,2,9,7}

构造以权值为叶子的哈夫曼树52677131629第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树构造完成127例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100128指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。三、前缀编码利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。129哈夫曼树的应用——编码各类编码ABCD等长编码00011011报文总长可以缩短不等长编码010011存在多义性0000AAAAAACACA前缀编码010110111一组编码中任何一个编码均不为其他编码的前缀.避免了多义性，且缩短了报文总长哈夫曼编码通过建立哈夫曼树得到最优的二进制前缀编码130哈夫曼编码

主要用途是实现数据压缩。

设给出一段报文：

CASTCASTSATATATASA

字符集合是{C,A,S,T}，各个字符出现的频度(次数)是W＝{2,7,4,5}。

若给每个字符以等长编码

A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36.

若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。因各字符出现的概率为{2/18,7/18,4/18,5/18}。131化整为{2,7,4,5}，以它们为各叶结点上的权值，建立哈夫曼树。左分支赋0，右分支赋1，得哈夫曼编码(变长编码)。

A:0T:10C:110S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。哈夫曼编码是一种无前缀的编码。解码时不会混淆。132哈夫曼编码的实现方法假设七个字符A,B,C,D,E,F,G在某次通信中出现的次数为4,2,6,8,3,2,1,设计这七个字符的哈夫曼编码。其过程如下:设置数组ht[m]表示哈夫曼树,每个数组元素表示一个结点,每个结点由w,p,l,r组成,表示权值,双亲,左孩子和右孩子.(1)初始态时在ht[m]的前n项存放编号为1~n的权值;133(2)依次将数组ht[m]的n+1项到第2n-1项做为当前项,进行如下处理:①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;③将两个选择项的权值相加后填入当前项做为当前项的权值;(3)由形成的哈夫曼树求哈夫曼编码:由根结点到叶结点,左分支为0,右分支为1;134初始态时在ht[m]的前n项存放编号为1~n的权值;

wplr14223648536271135①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr14223648536287188367136①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr14229364853962871883679525137①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr14102293648539628718831067952510718138①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr141022936114853962871883106795112510718111139139①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr14102293611481253962871883106795112510712181111391215410140①在前面已经形成的项目中选择两个权值最小且无双亲的项做为选择项;

②将当前项的序号填入两个选择项做为双亲,将两个选择项的序号填入当前项做为左右孩子;

③将两个选择项的权值相加后填入当前项做为当前项的权值;wplr141022936114812539628718831067951125107121811111339121513410132401112141哈夫曼树的建树265336221741841210891113142哈夫曼编码的确定1110201030041050116111071111对每个叶结点都进行如下的处理，扫描由叶结点到根结点的各条分支：

(1)若分支中的当前结点与双亲结点是左支关系，则生成编码0；

(2)若分支中的当前结点与双亲结点是右支关系，则生成编码1；由此生成的二进制码的序列即为该结点的哈夫曼编码。143哈夫曼树的编码过程wplr141022936114812539628718831067951125107121811111339121513410132401112144145网络信息传输：文字数字编码电信号电文编码发送者数字编码文字电文编码接收者你好0101010101你好核心问题：电文如何编码称为01串？？146项目实现的进一步分析：项目核心问题：如何将电报文字转换成01编码扩展问题：电文传送时的高效性147扩展问题：电文传送时的高效性在计算机及通信中，常用二进制编码来表示字符，假设某电文通信中只使用ABCD四个字符每个字母用两位二进制数表示，例如传输100个字母需要用200个二进制位此种编码方式为等长编码，此时电文长度由电文字符数决定对于电文：DABC可翻译为编码：对于编码：01001110可准确翻译为：00表示A01表示B10表示C11表示DBADC11000110148实际情况：字符在实际使用中出现频率不一样！新问题1：如何让电文编码缩短为提高电文传送效率，应让电文编码尽量短考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度常用汉字6335个，最常用字560个，常用字807个，次常用字1033个，共2400个。这些字占了书刊物汉字出现次数的99%A8.19B1.47C3.83D3.91E12.25F2.26G1.71H4.57I7.10J0.14K0.41L3.77………

前面十位是：ETAOINRSDC149假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：000011001000考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：问题：传输100个字母所用的二进制位为电文：ACDBA翻译成编码：编码：000011001翻译成电文:3×5+3×10+2×151×70+=145ACDB150此种编码方式为不等长编码，采用不等长编码可缩短电文编码长度，从而提高电文传送效率假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：151假定：翻译：CBDB翻译：CBDCD新问题2：随意的不等长编码可能导致编码翻译时出现歧义编码：000011001问题：编码是任意给定的吗？000表示A001表示B00表示C1表示D假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%000011001000011001000011001错误！错误！152新知识：设计不等长编码时，必须做到：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为前缀码新问题2：随意的不等长编码可能导致编码翻译时出现歧义000表示A001表示B01表示C1表示D我们设计的第一种编码是前缀码新问题3：如何设计前缀码153知识点4：哈夫曼树与哈夫曼编码树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积路径：若树中存在一个序列k1，k2…kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数154知识点4：哈夫曼树与哈夫曼编码树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到根结点之间的