(13)--第4章 树和二叉树数据结构.ppt

《(13)--第4章 树和二叉树数据结构.ppt》由会员分享，可在线阅读，更多相关《(13)--第4章 树和二叉树数据结构.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 树和二叉树教学目标1.1.掌握二叉树的基本概念、掌握二叉树的基本概念、性质性质和存储结构和存储结构2.2.熟练掌握二叉树的熟练掌握二叉树的前、中、后序遍历方法前、中、后序遍历方法3.3.了解了解线索化线索化二叉树的思想二叉树的思想4.4.熟练掌握：熟练掌握：哈夫曼树哈夫曼树的实现方法、构造的实现方法、构造哈夫哈夫曼编码曼编码的方法的方法5.5.了解：森林与二叉树的转换，树的遍历方法了解：森林与二叉树的转换，树的遍历方法主要内容主要内容5.1 5.1 树和二叉树的定义树和二叉树的定义5.2 5.2 树和二叉树的抽象数据类型定义树和二叉树的抽象数据类型定义5.3 5.3 二叉树的性质和存储

2、结构二叉树的性质和存储结构5.4 5.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树5.5 5.5 树和森林树和森林5.6 5.6 哈夫曼树及其应用哈夫曼树及其应用5.7 5.7 案例分析与实现案例分析与实现5.1 树和二叉和二叉树的定的定义树（树（TreeTree）是）是n n（n n0 0）个结点的有限集，它或为空）个结点的有限集，它或为空树（树（n n=0=0）；或为非空树，对于非空树）；或为非空树，对于非空树T T：（1 1）有且仅有一个称之为根的结点；）有且仅有一个称之为根的结点；（2 2）除根结点以外的其余结点可分为）除根结点以外的其余结点可分为m m（m m0 0）个）个互不相

3、交的有限集互不相交的有限集T T1 1,T T2 2,T Tm m,其中每一个集合本其中每一个集合本身又是一棵树，并且称为根的子树（身又是一棵树，并且称为根的子树（SubTreeSubTree）。）。树的定义树的定义树是是n个个结点的有限集点的有限集T1T2T3凹入表示凹入表示嵌套集合嵌套集合广广义表表树的其它表示方式的其它表示方式根叶子森林有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。基本基本术语即上即上层的那个的那个结点点(直接前直接前驱)即下即下层结点的子点的子树的根

4、的根(直接后直接后继)同一双同一双亲下的同下的同层结点（孩子之点（孩子之间互称兄弟）互称兄弟）即双即双亲位于同一位于同一层的的结点（但并非同一双点（但并非同一双亲）即从根到即从根到该结点所点所经分支的所有分支的所有结点点即即该结点下点下层子子树中的任一中的任一结点点双亲孩子兄弟堂兄弟祖先子孙基本基本术语即即树的数据元素的数据元素结点挂接的子点挂接的子树数数结点点结点的度点的度结点的点的层次次终端端结点点分支分支结点点树的度的度树的深度的深度(或高度或高度)从根到从根到该结点的点的层数（根数（根结点算第一点算第一层）即度即度为0的的结点，即叶子点，即叶子即度不即度不为0的的结点（也称点（也称为内

5、部内部结点）点）所有所有结点度中的最大点度中的最大值指所有指所有结点中最大的点中最大的层数数层次1234基本基本术语二叉树（二叉树（Binary TreeBinary Tree）是）是n n（n n0 0）个结点所构成的集合，）个结点所构成的集合，它或为空树（它或为空树（n n=0=0）；或为非空树，对于非空树）；或为非空树，对于非空树T T：（1 1）有且仅有一个称之为根的结点；）有且仅有一个称之为根的结点；（2 2）除根结点以外的其余结点分为两个互不相交的子集）除根结点以外的其余结点分为两个互不相交的子集T T1 1和和T T2 2，分别称为，分别称为T T的左子树和右子树，且的左子树和右

6、子树，且T T1 1和和T T2 2本身又本身又都是二叉树。都是二叉树。二叉树的定义二叉树的定义普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每何要重点研究每结点最多只有两个点最多只有两个“叉叉”的的树？二叉二叉树的的结构最构最简单，规律性最律性最强；可以可以证明，所有明，所有树都能都能转为唯一唯一对应的二叉的二叉树，不，不失一般性。失一般性。二叉树基本特点：结点的度小于等于结点的度小于等于2 2 有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）二叉树的五种不同形态二叉树的五种不同形态2/8/2024具有具有3 3个结点的二叉树可能有几种不同形态个结点的二叉树可能有几种

7、不同形态？树形如何？树形如何？1235ABCD提交单选题1分2/8/2024具有具有3 3个结点个结点的普通树可能的普通树可能有几种不同形态有几种不同形态？树形如何？树形如何？1235ABCD提交单选题1分5.2 树和二叉和二叉树的抽象数据的抽象数据类型定型定义ADT BinaryTree数据数据对象象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则R=；若若D，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的关于根的说明明 DjDk=/关于子关于子树不相交的不相交的说明明 /关于数据元素的关于数据元素的说明明 /关于左子关于左子树和

8、右子和右子树的的说明明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个二叉二叉树的抽象数据的抽象数据类型定型定义CreateBiTree(&T,definition)CreateBiTree(&T,definition)初始条件；初始条件；definitiondefinition给出二叉树给出二叉树T T的定义。的定义。操作结果：按操作结果：按definitiondefinition构造二叉树构造二叉树T T。PreOrderTraverse(T)PreOrderTraverse(T)初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：先序遍历操

9、作结果：先序遍历T T，对每个结点访问一次。，对每个结点访问一次。InOrderTraverse(T)InOrderTraverse(T)初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：中序遍历操作结果：中序遍历T T，对每个结点访问一次。，对每个结点访问一次。PostOrderTraverse(T)PostOrderTraverse(T)初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：后序遍历操作结果：后序遍历T T，对每个结点访问一次。，对每个结点访问一次。5.3 二叉二叉树的性的性质和存和存储结构构性质1:在二叉树的第i层上至多有2 2i-1i-1个结点提问：第i

10、层上至少有个结点？性质2:深度为k的二叉树至多有2 2k k-1-1个结点提问：深度为k时至少有个结点？1k深度为深度为5的完全二叉树的结点数不可能是的完全二叉树的结点数不可能是15161718ABCD提交单选题1分性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n21（即n0=n2+1）2/8/2024已知二叉树中，有已知二叉树中，有100100个度为个度为0 0的结点，那么的结点，那么二叉树中二叉树中至少至少有（有（）个）个结点结点200199101条件不足，没法计算ABCD提交单选题1分2/8/2024二叉树中有二叉树中有140140个结点，有个结点，有4040个度

11、为个度为1 1的结点的结点，则（则（）该二叉树中有该二叉树中有51个叶子结点个叶子结点该二叉树中有该二叉树中有50个个叶子叶子结点结点该二叉树中有该二叉树中有51个度为个度为2的结点的结点不可能有这样的二叉树不可能有这样的二叉树ABCD提交单选题1分满二叉树：一棵深度为一棵深度为k k 且有且有2 2k-1-1个结点的二叉树。个结点的二叉树。（特点：每层都“充满”了结点）特殊形特殊形态的二叉的二叉树完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边满二二叉叉树是是叶叶子子一一个个也也不不少

12、少的的树，而而完完全全二二叉叉树虽然然前前n-1层是是满的的，但但最最底底层却却允允许在在右右边缺缺少少连续若干个若干个结点。点。满二叉二叉树是完全二叉是完全二叉树的一个特例。的一个特例。满二叉二叉树和完全二叉和完全二叉树的区的区别深度为深度为7的完全二叉树中共有的完全二叉树中共有125个结点，则该个结点，则该完全二叉树中的叶子结点数为完全二叉树中的叶子结点数为（）62636465ABCD提交单选题1分性质性质4:4:具有具有n个个结点的完全二叉点的完全二叉树的深度必的深度必为 log2n+1k层层nk-1层层2k11n2k1或2k1n2kk1log2nk，因为k是整数所以k=log2n+12

13、/8/2024二叉树中，有二叉树中，有10251025个结点，则二叉树个结点，则二叉树最高高度最高高度是是多少？多少？最低高度最低高度是多少？是多少？作答正常使用主观题需2.0以上版本雨课堂主观题10分性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2。二叉二叉树的的顺序存序存储实现：按实现：按实现：按实现：按满二叉树满二叉树满二叉树满二叉树的结点层次编号，依次存放二叉树中的数的结点层次编号，依次存放二叉树中的数的结点层次编号，依次存放二叉树中的数的结点层次编号，依次存放二叉树中的数据元素。据元素。据元素。据

14、元素。abcde0000fg012345678910abcdefg特点：特点：特点：特点：结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中浪费空间，适于存浪费空间，适于存浪费空间，适于存浪费空间，适于存满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树 单支树单支树二叉二叉树的的顺序存序存储DATAPARENTPARENTLCHILDLCHILDRCHILDRCHILD二叉二叉树的的链式存式存储ABCDEFGABCDEFG二叉二叉链表表typedef struct BiNode TElemType d

15、ata;struct BiNode *lchild,*rchild;/左右孩子指左右孩子指针BiNode,*BiTree;分分析析：必必有有2n个个链域域。除除根根结点点外外，每每个个结点点有有且且仅有有一一个个双双亲，所所以以只只会会有有n1个个结点点的的链域域存存放放指指针，指向非空子女指向非空子女结点。点。空指空指针数目数目2n(n-1)=n+1在n个结点的二叉链表中，有 个空指针域练习ABCDEFGn+1三叉三叉链表表ABCDEFGABCDEFGlchilddataparentrchildtypedef struct TriTNodetypedef struct TriTNode Te

16、lemType data;TelemType data;struct TriTNode struct TriTNode*lchild,*parent,*rchild*lchild,*parent,*rchild;TriTNode,*TriTree;TriTNode,*TriTree;5.4 遍遍历二叉二叉树和和线索二叉索二叉树遍遍历定定义指按某条搜索路指按某条搜索路线遍遍访每个每个结点且点且不重复（又称周游）。不重复（又称周游）。遍遍历用途用途它是它是树结构插入、构插入、删除、修改、除、修改、查找和排序运算的前提，是二叉找和排序运算的前提，是二叉树一一切运算的基切运算的基础和核心。和核心。DL

17、RDLRLDRLRDDRLRDLRLD遍遍历规则先左后右先序遍先序遍历：中序遍中序遍历：后序遍后序遍历：ABCDEA B D E CA B D E CD D B E A CB E A CD E B C AD E B C A口口诀：DLR先序遍先序遍历，即先根再左再右，即先根再左再右LDR中序遍中序遍历，即先左再根再右，即先左再根再右LRD后序遍后序遍历，即先左再右再根，即先左再右再根+*A*/EDCB先序遍历+*/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB用二叉用二叉树表示算表示算术表达式表达式DLRADLRDLRBDCDL

18、RADBC先序遍历序列：先序遍历序列：A B D CA B D C若二叉若二叉树为空，空，则空操作空操作否否则访问根根结点点(D)前序遍前序遍历左子左子树(L)前序遍前序遍历右子右子树(R)遍历的算法实现先序遍历遍历的算法实现先序遍历则三种遍历算法可写出:遍历的算法实现遍历的算法实现用递归形式格外简单！用递归形式格外简单！用递归形式格外简单！用递归形式格外简单！longFactorial(longn)if(n=0)return1;/基本项elsereturnn*Factorial(n-1);/归纳项回忆:StatusPreOrderTraverse(BiTreeT)if(T=NULL)retu

19、rnOK;/空二叉树elsecoutdata;/访问根结点PreOrderTraverse(T-lchild);/递归遍历左子树PreOrderTraverse(T-rchild);/递归遍历右子树先序遍历算法先序遍历算法 2024年年2月月8日日 北京林业大学信息学院北京林业大学信息学院Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;else coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);主程序主程序Pre(T)返回返回pre(TR);返回返回pre(TR

20、);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T左是空返回pre(TR);T左是空返回T右是空返回T左是空返回T右是空返回pre(TR);先序序列：先序序列：ABDC遍历的算法实现中序遍历遍历的算法实现中序遍历若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作否则否则否则否则:中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L)(L)(L)(L)访问根结点访问根结点访问根结点访问根结点 (D)(D)(D)(D

21、)中序遍历右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R)(R)(R)(R)ADBCLDRBLDRLDRADCLDR中序遍历序列：中序遍历序列：B D A CB D A C中序遍历算法中序遍历算法StatusInOrderTraverse(BiTreeT)if(T=NULL)returnOK;/空二叉空二叉树elseInOrderTraverse(T-lchild);/递归遍遍历左子左子树coutdata;/访问根根结点点InOrderTraverse(T-rchild);/递归遍遍历右子右子树遍历的算法实现后序遍历遍历的算法实现后序遍历若二叉若二叉树为空，空，则空操作空操作否否则后序

22、遍后序遍历左子左子树(L)后序遍后序遍历右子右子树(R)访问根根结点点(D)ADBCLRDLRDLRDADCLRDB后序遍历序列：后序遍历序列：D B C AD B C A后序遍历算法后序遍历算法StatusPostOrderTraverse(BiTreeT)if(T=NULL)returnOK;/空二叉空二叉树elsePostOrderTraverse(T-lchild);/递归遍遍历左子左子树PostOrderTraverse(T-rchild);/递归遍遍历右子右子树coutdata;/访问根根结点点如图二叉树，后序序列为：ABDEGCFHDBGEAFHCDGEBHFCAABCDEFGH

23、ABCD提交单选题1分遍遍历算法的分析算法的分析StatusPreOrderTraverse(BiTreeT)if(T=NULL)returnOK;elsecoutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);StatusPostOrderTraverse(BiTreeT)if(T=NULL)returnOK;elsePostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);coutdata;StatusInOrderTraverse(BiTreeT)if(T=NULL

24、)returnOK;elseInOrderTraverse(T-lchild);coutdata;InOrderTraverse(T-rchild);如果去掉如果去掉输出出语句，从句，从递归的角度看，三种算法是完全相的角度看，三种算法是完全相同的，或同的，或说这三种算法的三种算法的访问路径是相同的，只是路径是相同的，只是访问结点的点的时机不同机不同。从虚从虚线的出的出发点到点到终点的路径点的路径上，每个上，每个结点点经过3次次。AFEDCBG第第1次次经过时访问先序先序遍遍历第第2次次经过时访问中序中序遍遍历第第3次次经过时访问后序后序遍遍历遍遍历算法的分析算法的分析AFEDCBG时间效率时间

25、效率:O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n):O(n)/栈占用的最大辅助空间栈占用的最大辅助空间遍遍历算法的分析算法的分析ABCDEFGABCDEFG按先序遍按先序遍历序列建立二叉序列建立二叉树的二叉的二叉链表表例：已知先序序列例：已知先序序列为：A B C D E G F （动态演示）演示）二叉二叉树的建立（算法的建立（算法5.3）二叉二叉树的建立（算法的建立（算法5.3）void CreateBiTree(BiTree&T）cinch;if(ch=#)T=NULL;/递归结束，建空束，建空树else T=new BiTNode;T-data=ch;

26、/生成根生成根结点点CreateBiTree(T-lchild);/递归创建左子建左子树CreateBiTree(T-rchild);/递归创建右子建右子树计算二叉算二叉树结点点总数数二叉二叉树遍遍历算法的算法的应用用如果是空如果是空树，则结点个数点个数为0；否否则，结点个数点个数为左子左子树的的结点个数点个数+右子右子树的的结点个数点个数再再+1。int NodeCount(BiTree T)if(T=NULL)return 0;else return NodeCount(T-lchild)+NodeCount(T-rchild)+1;计算二叉树叶子结点总数二叉二叉树遍遍历算法的算法的应用用

27、如果是空树，则叶子结点个数为0；否则，为左子树的叶子结点个数+右子树的叶子结点个数。？int LeadCount(BiTree T)if(T=NULL)/如果是空如果是空树返回返回0return 0;if(T-lchild=NULL&T-rchild=NULL)return 1;/如果是叶子如果是叶子结点返回点返回1else return LeafCount(T-lchild)+LeafCount(T-rchild);计算二叉树深度二叉二叉树遍遍历算法的算法的应用用如果是空如果是空树，则深度深度为0；否否则，递归计算左子算左子树的深度的深度记为m，递归计算右子算右子树的深度的深度记为n，二叉，

28、二叉树的深度的深度则为m与与n的的较大者加大者加1。若二叉若二叉树中各中各结点的点的值均不相同，均不相同，则：由二叉由二叉树的前序序列和中序序列，或由其后序序列和中序的前序序列和中序序列，或由其后序序列和中序序列均序列均能唯一能唯一地确定一棵二叉地确定一棵二叉树，但由前序序列和后序序列却但由前序序列和后序序列却不一定能唯一不一定能唯一地确定一棵二叉地确定一棵二叉树。重要重要结论某二叉树的前序序列为某二叉树的前序序列为ABCD，中序序列为，中序序列为DCBA，则后序序列为，则后序序列为BADCDCBACDABABCDABCD提交单选题1分2/8/2024已知一棵二叉已知一棵二叉树的的中序序列中序

29、序列和和后序序列后序序列分分别是是BDCEAFHG 和和 DECBHGFA，请画出画出这棵二棵二叉叉树。作答正常使用主观题需2.0以上版本雨课堂主观题10分思考思考二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。线索化二叉索化二叉树在n个结点的二叉链表中，有n+1个空指针域ABCDEFG线索化二叉索化二叉树普通二叉普通二叉树只能找到只能找到结点的左右孩子信息，而点的左右孩子信息，而该结点的点的直接前直接前驱和直接后和直接后继只能在遍只能在遍历过程中程中获得得若将遍若将遍历后后对应的有关前的有关前驱和后和后继预存起来，

30、存起来，则从从第一第一个个结点点开始就能很快开始就能很快“顺藤摸瓜藤摸瓜”而遍而遍历整个整个树例如中序遍例如中序遍历结果：果：B D C E A F H G，实际上上已将二已将二叉叉树转为线性排列，性排列，显然具有唯一前然具有唯一前驱和唯一后和唯一后继！可能是根、或最左（右）叶子两种解决方法增加两个域：fwd和bwd；利用空链域（n+1个空链域）如何保存如何保存这类信息？信息？线索化二叉索化二叉树1）若）若结点有左子点有左子树，则lchild指向其左孩子；指向其左孩子；否否则，lchild指向其直接前指向其直接前驱(即即线索索)；2）若）若结点有右子点有右子树，则rchild指向其右孩子；指向

31、其右孩子；否否则，rchild指向其直接后指向其直接后继(即即线索索)。为了避免混淆，增加两个了避免混淆，增加两个标志域志域lchildLTagdataRTag rchild线索化二叉索化二叉树LTag :若若 LTag=0,lchild域指向左孩子；域指向左孩子；若若 LTag=1,lchild域指向其前域指向其前驱。RTag :若若 RTag=0,rchild域指向右孩子；域指向右孩子；若若 RTag=1,rchild域指向其后域指向其后继。lchildLTagdataRTag rchild线索化二叉索化二叉树先序先序线索二叉索二叉树ABCDEABDCET先序序列：先序序列：ABCDE00

32、00111111lchildLTagdataRTagrchildLTag=0,lchild域指向左孩子域指向左孩子LTag=1,lchild域指向其前域指向其前驱RTag=0,rchild域指向右孩子域指向右孩子RTag=1,rchild域指向其后域指向其后继 中序中序线索二叉索二叉树ABCDEABDCET中序序列：中序序列：BCAED0000111111lchildLTagdataRTagrchild后序后序线索二叉索二叉树lchildLTagdataRTagrchildABCDEABDCET后序序列：后序序列：CBEDA0000111111线索索：指向：指向结点前点前驱和后和后继的指的指针

33、线索索链表表：加上：加上线索二叉索二叉链表表线索二叉索二叉树：加上：加上线索的二叉索的二叉树（图形式形式样）线索化索化：对二叉二叉树以某种次序遍以某种次序遍历使其使其变为线索索二叉二叉树的的过程程线索化二叉索化二叉树的几个的几个术语ABCGEIDHFroot悬悬空？空？悬悬空？空？该二叉二叉树中序遍中序遍历结果果为:H,D,I,B,E,A,F,C,G画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点练习对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：00A00C00B11E1

34、1F11G00D11I11H注：此注：此图中序遍中序遍历结果果为:H,D,I,B,E,A,F,C,G0-root0画出与二叉树对应的中序线索二叉树2825405560330854因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL练习5.5 树和森林和森林树的存的存储结构二叉构二叉链表表示法表表示法typedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;树的存的存储结构二叉构二叉链表表示法表表示法 树 二叉

35、二叉树 对应 存存储 存存储 解解释 解解释游游戏戏中中主主角角的的生生命命值值d d，有有这这样样的的条条件件判判定定：当当怪怪物物碰碰到到主主角角后后，怪怪物物的的反反应应遵遵从从下下规则规则:5.6 5.6 哈夫曼树及其应用哈夫曼树及其应用if(d100)state=嘲笑，单挑嘲笑，单挑;else if(d200)state=单挑单挑;else if(d300)state=嗜血魔法嗜血魔法;else if(d=200)&(d=300)&(d=100)&(d200)state=单挑单挑;else if(d100)state=嘲笑，单挑嘲笑，单挑;else state=逃跑逃跑;if(d10

36、0)state=嘲笑，单挑嘲笑，单挑;else if(d200)state=单挑单挑;else if(d300)state=嗜血魔法嗜血魔法;else if(d500)state=呼唤同伴呼唤同伴;else state=逃跑逃跑;在在远程通程通讯中，要将待中，要将待传字符字符转换成二成二进制的字符串，制的字符串，怎怎样编码才能使它才能使它们组成的成的报文在网文在网络中中传得最快？得最快？ABACCDA000110010101100000011010哈夫曼哈夫曼树应用用实例哈夫曼例哈夫曼编码出现次数较多的字符采用尽可能短的编码哈夫曼哈夫曼树应用用实例哈夫曼例哈夫曼编码关关键：要要设计长度不等的度

37、不等的编码，则必必须使任一字符使任一字符的的编码都不是另一个字符的都不是另一个字符的编码的的前前缀前前缀编码0000AAAAABABB重码ABACCDA000011010ACBD000111采用二叉树设计前缀编码左分支用“0”右分支用“1”A0B110C10D111 0110010101110ABACCDA分解接收字符串：遇分解接收字符串：遇“0”向左，遇向左，遇“1”向右；向右；一旦到达叶子一旦到达叶子结点，点，则译出一个字符，反复由根出一个字符，反复由根出出发，直到，直到译码完成。完成。0110010101110ACBD000111ABACCDA特点：每一码都不是另一码的前缀，绝不会错译!

38、称为前缀码哈夫曼哈夫曼编码的的译码过程程路路径径：路径路径长度度：带权路径路径长度度：树的的带权路径路径长度度：哈哈 夫夫 曼曼 树：由一由一结点到另一点到另一结点点间的分支所构成的分支所构成路径上的分支数目路径上的分支数目结点到根的路径点到根的路径长度与度与结点上点上权的乘的乘积debacf g树中所有叶子中所有叶子结点的点的带权路径路径长度之和度之和带权路径路径长度最小的度最小的树ae的路径长度2WPL=wklk k=1n哈夫曼哈夫曼树的构造的构造dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=

39、7*2+5*2+2*2+4*2=36权值分分别为7，5，2，4，构造有，构造有4个叶子个叶子结点的二叉点的二叉树a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4哈夫曼哈夫曼树的构造的构造过程程操作要点：操作要点：对权值的的合并、合并、删除与替除与替换，总是合并当前是合并当前值最小的两个最小的两个基本思想：基本思想：使使权大的大的结点靠近根点靠近根基本思想：概率大的字符用短基本思想：概率大的字符用短码，小的用，小的用长码，构造哈夫，构造哈夫曼曼树哈夫曼哈夫曼编码的构造的构造例：某系例：某系统在通在通讯时，只出，只出现C，A，S，T，B五种字符，五种字符，

40、其出其出现频率依次率依次为2，4，2，3，3，试设计Huffman编码。148464220001113301TBACST00B01A10C110S111例例5.2根据根据给定的定的n个个权值 w1,w2,wn，构造构造n棵只有根棵只有根结点的二叉点的二叉树。在森林中在森林中选取两棵根取两棵根结点点权值最小的最小的树作左右子作左右子树，构，构造一棵新的二叉造一棵新的二叉树，置新二叉，置新二叉树根根结点点权值为其左右子其左右子树根根结点点权值之和。之和。在森林中在森林中删除除这两棵两棵树，同，同时将新得到的二叉将新得到的二叉树加入森加入森林中。林中。重复上述两步，重复上述两步，直到只含一棵直到只含

41、一棵树为止止，这棵棵树即即哈夫哈夫曼曼树。哈夫曼哈夫曼树的构造的构造过程程typedef struct int weght;int parent,lch,rch;*HuffmanTree;哈夫曼哈夫曼树构造算法的构造算法的实现（算法（算法5.10）采用采用顺序存序存储结构构一一维结构数构数组结点点类型定型定义一棵有一棵有n个叶子个叶子结点的点的Huffman树有有个个结点点2n-11)初始化初始化HT1.2n-1：lch=rch=parent=02)输入初始入初始n个叶子个叶子结点：置点：置HT1.n的的weight值3)进行以下行以下n-1次合并，依次次合并，依次产生生HTi，i=n+1.2

42、n-1：3.1)在在HT1.i-1中中选两个未被两个未被选过的的weight最小的两个最小的两个结点点HTs1和和HTs2(从从parent=0 的的结点中点中选)3.2)修改修改HTs1和和HTs2的的parent值：parent=i 3.3)置置HTi：weight=HTs1.weight+HTs2.weight,lch=s1,rch=s2哈夫曼哈夫曼树构造算法的构造算法的实现例例:设n=4,w=70,50,20,40试设计 huffman code(m=2*4-1=7)weightparentlchrch170000250000320000440000567weightparentlch

43、rch17070025060032050044050056063461107257180016a70b50c20d40 2024年年2月月8日日 算法算法void CreatHuffmanTree(HuffmanTree HT,int n)if(n=1)return;m=2*n-1;HT=new HTNodem+1;/0号单元未用，号单元未用，HTm表示根结点表示根结点 for(i=1;i=m;+i)HTi.lch=0;HTi.rch=0;HTi.parent=0;for(i=1;iHTi.weight;weightparentlchrch115529781423311000000000000

44、000例例:设设n=8,w=5,29,7,8,14,23,3,11试设计试设计 huffman code(m=2*8-1=15)000000000000000000000000000000for(i=n+1;i=m;+i)/构造构造 Huffman树树 Select(HT,i-1,s1,s2);/在在HTk(1ki-1)中选择两个其双亲域为中选择两个其双亲域为0,/且权值最小的结点且权值最小的结点,/并返回它们在并返回它们在HT中的序号中的序号s1和和s2 HTs1.parent=i;HTs2.parent=i;/表示从表示从F中删除中删除s1,s2 HTi.lch=s1;HTi.rch=s2

45、;/s1,s2分别作为分别作为i的左右孩子的左右孩子 HTi.weight=HTs1.weight+HTs2.weight;/i 的权值为左右孩子权值之和的权值为左右孩子权值之和 weightparentlchrch1155297814233118151929425810091410101213911111213141515013856274910111214000000000000000013构造构造Huffman tree后后,HT为:void CreatHuffmanCode(HuffmanTree HT,HuffmanCode&HC,int n)/从叶子到根逆向求每个字符的赫夫曼编码，

46、存储在编码表从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中中HC=new char*n+1;/分配分配n个字符编码的头指针矢量个字符编码的头指针矢量cd=new char n;/分配临时存放编码的动态数组空间分配临时存放编码的动态数组空间cdn-1=0;/编码结束符编码结束符for(i=1;i=n;+i)/逐个字符求赫夫曼编码逐个字符求赫夫曼编码 start=n-1;c=i;f=HTi.parent;while(f!=0)/从叶子结点开始向上回溯，直到根结点从叶子结点开始向上回溯，直到根结点 -start;/回溯一次回溯一次start向前指一个位置向前指一个位置 if(HTf.lch

47、ild=c)cdstart=0;/结点结点c是是f的左孩子，则生成代码的左孩子，则生成代码0 else cdstart=1;/结点结点c是是f的右孩子，则生成代码的右孩子，则生成代码1 c=f;f=HTf.parent;/继续向上回溯继续向上回溯 /求出第求出第i个字符的编码个字符的编码 HCi=new char n-start;/为第为第i 个字符编码分配空间个字符编码分配空间 strcpy(HCi,&cdstart)；/将求得的编码从临时空间将求得的编码从临时空间cd复制到复制到HC的当前行中的当前行中 delete cd;/释放临时空间释放临时空间/CreatHuffanCode哈夫曼编

48、码是哈夫曼编码是不等长编码不等长编码哈夫曼编码是哈夫曼编码是前缀编码前缀编码，即任一字符的编码都不是另一，即任一字符的编码都不是另一字符编码的前缀字符编码的前缀哈夫曼编码树中没有度为哈夫曼编码树中没有度为1 1的结点。若叶子结点的个数的结点。若叶子结点的个数为为n n，则哈夫曼编码树的，则哈夫曼编码树的结点总数为结点总数为 2n-12n-1发送过程：根据由发送过程：根据由哈夫曼树得到的编码表哈夫曼树得到的编码表送出字符数据送出字符数据接收过程：按接收过程：按左左0 0、右、右1 1的规定，从根结点走到一个叶结的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据点，完成一个字符的译码。反复此过程，直到接收数据结束结束哈夫曼编码的几点结论哈夫曼编码的几点结论1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表树二叉树森林中序遍历后序遍历先序遍历哈夫曼树哈夫曼编码小结