树和二叉树数据结构

数据结构数据结构线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构第第6 6章树章树和二叉树和二叉树6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树6.4 树和森林树和森林6.5 霍夫曼树及其应用霍夫曼树及其应用1.1.掌握二叉树的基本概念、掌握二叉树的基本概念、性质性质和存储结构和存储结构2.2.熟练掌握二叉树的熟练掌握二叉树的前、中、后序遍历方法前、中、后序遍历方法3.3.了解了解线索化线索化二叉树的思想二叉树的思想4.4.熟练掌握：熟练掌握：霍夫曼树霍夫曼树的实现方法、构造的实现方法、构造霍夫曼编霍夫曼编码码的方法的方法5.5.了解：森林与二叉树的转换，树的遍历方法了解：森林与二叉树的转换，树的遍历方法教学目标教学目标6.1 6.1 树的定义和基本术语树的定义和基本术语树是树是n n个结点的有限集个结点的有限集T1T2T3ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个树的抽象数据类型定义树的抽象数据类型定义凹入表示凹入表示嵌套集合嵌套集合广义表广义表树的其它表示方式树的其它表示方式 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合(例如删除例如删除A后的子树个数后的子树个数)结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。基本术语基本术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙基本术语基本术语即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值所有结点度中的最大值指所有结点中最大的层数指所有结点中最大的层数层次1234基本术语基本术语MINEBDAGJKCFLH 1)哪是根节点 2）哪是叶子节点 3）哪个节点是G的双亲 4）哪些是G的祖先 5）哪些节点是G的孩子 6）哪些节点是E的子孙 7）哪些节点是E的兄弟 8）节点B和N的层次号是 分别是多少 9）树的深度是多少 10）以节点C为根的子树 的深度是多少 11）树的度数是多少MINEBDAGJKCFLH6.2 6.2 二叉树二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不可以证明，所有树都能转为唯一对应的二叉树，不失一般性。失一般性。二叉树二叉树基本基本特点：特点：结点的度小于等于结点的度小于等于结点的度小于等于结点的度小于等于2 2 2 2有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）二叉树的五种不同形态二叉树的五种不同形态具有具有具有具有3 3 3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？练习练习5 5种种/2/2种种一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？解：解：二叉树是颗有序树，但度为2的树则未必有序。ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R=；若若D，则，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个二叉树的抽象数据类型定义二叉树的抽象数据类型定义性质性质1:1:在二叉树的第在二叉树的第i i层上至多有层上至多有2 2 2 2i-1i-1i-1i-1个结点个结点二叉树的性质二叉树的性质提问：第提问：第i i层上至少有层上至少有 个结点？个结点？性质性质2:2:深度为深度为k k的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点个结点提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？1k性质性质3:3:对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，则叶子数个，则叶子数n n0 0必定为必定为n n2 21 1（即（即n n0 0=n=n2 2+1+1）满二叉树：满二叉树：一棵深度为一棵深度为一棵深度为一棵深度为k k k k 且有且有且有且有2 2 2 2k k-1-1-1-1个结点的个结点的个结点的个结点的二叉树。二叉树。二叉树。二叉树。（特点：每层（特点：每层都都“充满充满”了结点）了结点）特殊形态的二叉树特殊形态的二叉树完全二叉树：完全二叉树：深度为深度为k k 的的，有有n n个结点的二叉树，当且个结点的二叉树，当且仅当其每一个结点都与深度仅当其每一个结点都与深度为为k k 的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点的结点一一对应一一对应只有最后一层叶子不满，只有最后一层叶子不满，且全部集中在左边且全部集中在左边满满二二叉叉树树是是叶叶子子一一个个也也不不少少的的树树，而而完完全全二二叉叉树树虽虽然然前前n-1n-1层层是是满满的的，但但最最底底层层却却允允许许在在右右边边缺缺少少连连续续若若干个结点。干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。满二叉树和完全二叉树的区别满二叉树和完全二叉树的区别一棵完全二叉树有一棵完全二叉树有50005000个结点，可以计算出其个结点，可以计算出其叶结点的个数是（叶结点的个数是（）。）。练习练习2500性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为loglog2 2n n1 1k层层nk-1层层性质性质5:5:对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i2i，其右孩子编号，其右孩子编号必为必为2i2i1 1；其双亲的编号必为；其双亲的编号必为i/2i/2。二叉树的顺序存储二叉树的顺序存储实现：按实现：按实现：按实现：按满二叉树满二叉树满二叉树满二叉树的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉树中的数据元素。树中的数据元素。树中的数据元素。树中的数据元素。a b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10abcdefg特点：特点：特点：特点：结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中浪费空间，适于存浪费空间，适于存浪费空间，适于存浪费空间，适于存满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树 单支树单支树二叉树的顺序存储二叉树的顺序存储DATADATAPARENTPARENTLCHILDLCHILDRCHILDRCHILD二叉树的链式存储二叉树的链式存储ABCDEFG AB C D E F G二叉链表二叉链表typedef struct BiNode TElemType data;struct BiNode *lchild,*rchild;/左右孩子指针左右孩子指针BiNode,*BiTree;分分析析：必必有有2n2n个个链链域域。除除根根结结点点外外，每每个个结结点点有有且且仅仅有有一一个个双双亲亲，所所以以只只会会有有n n1 1个个结结点点的的链链域域存存放放指指针针，指指向向非非空空子子女结点。女结点。空指针数目空指针数目2n2n(n-1)=n+1(n-1)=n+1在在n n个结点的二叉链表中，个结点的二叉链表中，有有 个个空指针域空指针域练习练习 AB C D E F Gn+1三叉链表三叉链表ABCDEFG A B C D E F Glchild data parent rchildtypedef struct TriTNodetypedef struct TriTNode TelemType data;TelemType data;struct TriTNode struct TriTNode*lchild,*parent,*rchild*lchild,*parent,*rchild;TriTNode,*TriTree;TriTNode,*TriTree;6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历定义遍历定义指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。遍历用途遍历用途它是树结构插入、删除、修改、查它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一找和排序运算的前提，是二叉树一切运算的基础和核心。切运算的基础和核心。DLRDLRLDRLRDDRLRDLRLD遍历规则遍历规则先左后右先左后右先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：A B CD EA B D E CA B D E CD B E A CD B E A CD E B C AD E B C A口诀：口诀：DLRDLR先序遍历，即先根再左再右先序遍历，即先根再左再右LDRLDR中序遍历，即先左再根再右中序遍历，即先左再根再右LRDLRD后序遍历，即先左再右再根后序遍历，即先左再右再根+*A*/EDCB先序遍历先序遍历+*/A B C D E前缀表示前缀表示中序遍历中序遍历A/B*C*D+E中缀表示中缀表示后序遍历后序遍历A B/C*D*E+后缀表示后缀表示层序遍历层序遍历+*E*D/C A B用二叉树表示算术表达式用二叉树表示算术表达式D L RAD L RD L RBDCD L RADBC先序遍历序列：先序遍历序列：先序遍历序列：先序遍历序列：A B D CA B D C若二叉树为空，则空操作若二叉树为空，则空操作否则否则访问根结点访问根结点 (D)(D)前序遍历左子树前序遍历左子树 (L)(L)前序遍历右子树前序遍历右子树 (R)(R)遍历的算法实现先序遍历遍历的算法实现先序遍历则三种遍历算法可写出则三种遍历算法可写出:遍历的算法实现遍历的算法实现用递归形式格外简单！用递归形式格外简单！用递归形式格外简单！用递归形式格外简单！long Factorial(long n)if(n=0)return 1;/基本项基本项 else return n*Factorial(n-1);/归纳项归纳项回忆回忆:Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else coutdata;/访问根结点访问根结点 PreOrderTraverse(T-lchild);/递归遍历左子树递归遍历左子树 PreOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 先序遍历算法先序遍历算法Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;else coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：先序序列：ABDC遍历的算法实现中序遍历遍历的算法实现中序遍历若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作否则否则否则否则:中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L)(L)(L)(L)访问根结点访问根结点访问根结点访问根结点 (D)(D)(D)(D)中序遍历右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R)(R)(R)(R)ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：中序遍历序列：中序遍历序列：B D A CB D A CB D A CB D A CStatus InOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else InOrderTraverse(T-lchild);/递归遍历左子树递归遍历左子树 coutdata;/访问根结点访问根结点 InOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 中序遍历算法中序遍历算法遍历的算法实现后序遍历遍历的算法实现后序遍历若二叉树为空，则空操作若二叉树为空，则空操作否则否则后序遍历左子树后序遍历左子树 (L)(L)后序遍历右子树后序遍历右子树 (R)(R)访问根结点访问根结点 (D)(D)ADBC L R DL R DL R DADCL R DB后序遍历序列：后序遍历序列：后序遍历序列：后序遍历序列：D B C AD B C AStatus PostOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else PostOrderTraverse(T-lchild);/递归遍历左子树递归遍历左子树 PostOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 coutdata;/访问根结点访问根结点 后序遍历算法后序遍历算法Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;else coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);Status PostOrderTraverse(BiTree T)if(T=NULL)return OK;else PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);coutdata;Status InOrderTraverse(BiTree T)if(T=NULL)return OK;else InOrderTraverse(T-lchild);coutdata;InOrderTraverse(T-rchild);遍历算法的分析遍历算法的分析如果去掉输出语句，从递归的角度看，三种算法是完如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的全相同的，或说这三种算法的访问路径是相同的，只访问路径是相同的，只是访问结点的时机不同是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问经过时访问先序先序遍历遍历第第2次次经过时访问经过时访问中序中序遍历遍历第第3次次经过时访问经过时访问后序后序遍历遍历遍历算法的分析遍历算法的分析AFEDCBG时间效率时间效率:O(nO(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(nO(n)/栈占用的最大辅助空间栈占用的最大辅助空间遍历算法的分析遍历算法的分析ABCDEFG A B C D E F G 按先序遍历序列建立二叉树的二叉链表按先序遍历序列建立二叉树的二叉链表例：已知先序序列为：例：已知先序序列为：A B C A B C D E D E G G F F （动态演示）（动态演示）二叉树的建立（算法二叉树的建立（算法6.36.3）计算二叉树结点总数计算二叉树结点总数计算计算二叉树二叉树叶子总数叶子总数计算二叉树高度计算二叉树高度二叉树遍历算法的应用二叉树遍历算法的应用若二叉树中各结点的值均不相同，则：若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和由二叉树的前序序列和中序序列，或由其后序序列和中序序列均中序序列均能唯一能唯一地确定一棵二叉树，地确定一棵二叉树，但由前序序列和后序序列却但由前序序列和后序序列却不一定能唯一不一定能唯一地确定一棵地确定一棵二叉树。二叉树。重要结论重要结论练习练习已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHGBDCEAFHG 和和 DECBHGFADECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（A A）；由由中中序序遍遍历历特特征征，根根结结点点必必在在其其中中间间，而而且且其其左左部部必必全全部部是是左左子子树树子子孙孙（BDCEBDCE），其其右右部部必必全全部部是是右右子子树子孙树子孙（FHGFHG）；继继而而，根根据据后后序序中中的的DECBDECB子子树树可可确确定定B B为为A A的的左左孩孩子子，根据根据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。中序遍历：中序遍历：B D C E A F H GB D C E A F H G后序遍历：后序遍历：D E C B H G F D E C B H G F A A（B D C E）（F H G）ABF （D C E）（H G）CD EGHABBFF二叉链表空间效率这么低，能否二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息利用这些空闲区存放有用的信息或线索？或线索？可以用它来存放当前结点的可以用它来存放当前结点的直接前驱和后继直接前驱和后继等线索，以加快等线索，以加快查找速度。查找速度。思考思考线索化二叉树线索化二叉树在在n n个结点的二叉链表中，个结点的二叉链表中，有有n+1n+1个个空指针域空指针域 AB C D E F G普通二叉树只能找到结点的左右孩子信息，而该普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则若将遍历后对应的有关前驱和后继预存起来，则从从第一个结点第一个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整个而遍历整个树树例如中序遍历结果：例如中序遍历结果：B D C E A F H GB D C E A F H G，实际上，实际上已已将二叉树转为线性排列，显然具有唯一前驱和唯将二叉树转为线性排列，显然具有唯一前驱和唯一后继！一后继！可能是根、或最左（右）叶子可能是根、或最左（右）叶子线索化二叉树线索化二叉树两种解决方法两种解决方法增加两个域：增加两个域：fwdfwd和和bwdbwd；利用空链域（利用空链域（n+1n+1个空链域）个空链域）如何保存这类信息？如何保存这类信息？线索化二叉树线索化二叉树1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子；否则，否则，lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子；否则，否则，rchild指向其直接后继指向其直接后继(即线索即线索)。为了避免混淆，增加两个标志域为了避免混淆，增加两个标志域lchildLTagdataRTag rchild线索化二叉树线索化二叉树LTagLTag :若若 LTagLTag=0,=0,lchildlchild域指向左孩子；域指向左孩子；若若 LTagLTag=1,=1,lchildlchild域指向其前驱。域指向其前驱。RTagRTag :若若 RTagRTag=0,=0,rchildrchild域指向右孩子；域指向右孩子；若若 RTagRTag=1,=1,rchildrchild域指向其后继。域指向其后继。lchildLTagdataRTag rchild线索化二叉树线索化二叉树ABCDE A B D C ET先序序列：先序序列：ABCDE0000111111 lchild LTag data RTag rchild先序线索二叉树先序线索二叉树LTagLTag=0,=0,lchildlchild域指向左孩子域指向左孩子LTagLTag=1,=1,lchildlchild域指向其前驱域指向其前驱RTagRTag=0,=0,rchildrchild域指向右孩子域指向右孩子RTagRTag=1,=1,rchildrchild域指向其后继域指向其后继 ABCDE A B D C ET中序序列：中序序列：BCAED0000111111 lchild LTag data RTag rchild中序线索二叉树中序线索二叉树 lchild LTag data RTag rchildABCDE A B D C ET后序序列：后序序列：CBEDA0000111111后序线索二叉树后序线索二叉树线索线索：指向结点前驱和后继的指针：指向结点前驱和后继的指针线索链表线索链表：加上线索二叉链表：加上线索二叉链表线索二叉树线索二叉树：加上线索的二叉树（图形式样）：加上线索的二叉树（图形式样）线索化线索化：对二叉树以某种次序遍历使其变为线索二叉：对二叉树以某种次序遍历使其变为线索二叉树的过程树的过程线索化二叉树的几个术语线索化二叉树的几个术语ABCGEIDHFroot悬空？悬空？悬空？悬空？该二叉树中序遍历结果为该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G画出以下二叉树对应的中序线索二叉树。画出以下二叉树对应的中序线索二叉树。画出以下二叉树对应的中序线索二叉树。画出以下二叉树对应的中序线索二叉树。为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点练习练习对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0-root0画出与二叉树对应的中序线索二叉树画出与二叉树对应的中序线索二叉树 2825405560330854因为中序遍历序列是：因为中序遍历序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454对应线索树应当按此规律连线，即对应线索树应当按此规律连线，即在原二叉树中添在原二叉树中添加虚线。加虚线。NILNILNILNIL练习练习平衡树平衡树排序树排序树判定树判定树带权树带权树最优树最优树特点：左右子树深度差特点：左右子树深度差 1 1特点：特点：“左小右大左小右大”例如，例如，1212个球只称个球只称3 3次分出轻重次分出轻重特点：路径长度带权值特点：路径长度带权值 带权路径长度最短的树，又称带权路径长度最短的树，又称 HuffmanHuffman树树，用途之一是通信中的压缩编码。，用途之一是通信中的压缩编码。二叉树的应用二叉树的应用6.5 6.5 霍夫曼树霍夫曼树6.4 6.4 树和森林树和森林树的存储结构二叉链表表示法树的存储结构二叉链表表示法typedef struct CSNode ElemType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;树的存储结构二叉链表表示法树的存储结构二叉链表表示法 树树 二叉二叉树树 对应对应 存储存储 存储存储 解释解释 解释解释6.5 6.5 霍夫曼树及其应用霍夫曼树及其应用路路 径径：路径长度路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积d de eb ba ac cf f g g树中所有叶子结点的带权路径长度之和树中所有叶子结点的带权路径长度之和带权路径长度最小的树带权路径长度最小的树aeae的路径长度的路径长度 2 2WPLWPL=w wk kl lk k k=1k=1n ndcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36权值分别为权值分别为7 7，5 5，2 2，4 4，构造有，构造有4 4个叶子结点的二叉树个叶子结点的二叉树a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼树的构造过程霍夫曼树的构造过程操作要点：操作要点：对权值的对权值的合并、删除与替换合并、删除与替换，总是，总是合并当前值最小的两个合并当前值最小的两个基本思想：基本思想：使权大的结点靠近根使权大的结点靠近根在远程通讯中，要将待传字符转换成二进制的字符串，在远程通讯中，要将待传字符转换成二进制的字符串，怎样编码才能使它们组成的报文在网络中传得最快？怎样编码才能使它们组成的报文在网络中传得最快？ABACCDA000110010101100000011010霍夫曼树应用实例霍夫曼编码霍夫曼树应用实例霍夫曼编码出现次数较多的字符采用尽可能短的编码出现次数较多的字符采用尽可能短的编码关键：关键：要设计长度不等的编码，则必须使任一字符的要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的编码都不是另一个字符的编码的前缀前缀前缀编码前缀编码0000AAAA ABA BB重码重码ABACCDA000011010霍夫曼树应用实例霍夫曼编码霍夫曼树应用实例霍夫曼编码ACBD000111采用二叉树设采用二叉树设计计前缀编码前缀编码左分支用左分支用“0 0”右分支用右分支用“1 1”A0B110C10D111 0110010101110 ABACCDA分解接收字符串：遇分解接收字符串：遇“0 0”向左，遇向左，遇“1 1”向右；一旦向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。到译码完成。0110010101110ACBD000111ABACCDA特点：每一码都不是另一码的前缀，绝不会错译特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码称为前缀码霍夫曼编码的译码过程霍夫曼编码的译码过程基本思想：概率大的字符用短码，小的用长码，构造霍基本思想：概率大的字符用短码，小的用长码，构造霍夫曼树夫曼树霍夫曼编码的构造霍夫曼编码的构造例：某系统在通讯时，只出现例：某系统在通讯时，只出现C C，A A，S S，T T，B B五种字符，其五种字符，其出现频率依次为出现频率依次为2 2，4 4，2 2，3 3，3 3，试设计，试设计HuffmanHuffman编码。编码。148464220001113301 T B A C ST 00B 01A 10 C 110 S 111例例6.2根据给定的根据给定的n n个权值个权值 w w1 1,w,w2 2,w wn n，构造构造n n棵只棵只有根结点的二叉树有根结点的二叉树。在森林中选取两棵根结点在森林中选取两棵根结点权值最小的树作左右子权值最小的树作左右子树树，构造一棵新的二叉树，置新二叉树根结点权，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。值为其左右子树根结点权值之和。在森林中在森林中删除这两棵树删除这两棵树，同时将新得到的二叉树，同时将新得到的二叉树加入森林中。加入森林中。重复上述两步，重复上述两步，直到只含一棵树为止直到只含一棵树为止，这棵树即，这棵树即霍霍夫曼树。夫曼树。霍夫曼树的构造过程霍夫曼树的构造过程Ch5_8.ctypedef struct int weght;int parent,lch,rch;*HuffmanTree;霍夫曼树构造算法的实现（算法霍夫曼树构造算法的实现（算法6.106.10）采用顺序存储结构采用顺序存储结构一维结构数组一维结构数组结点类型定义结点类型定义一棵有一棵有n n个叶子结点的个叶子结点的HuffmanHuffman树有树有 个结点个结点2n-11)1)初始化初始化HT1.2n-1HT1.2n-1：lchlch=rchrch=parent=0=parent=02)2)输入初始输入初始n n个叶子结点：置个叶子结点：置HT1.nHT1.n的的weightweight值值3)3)进行以下进行以下n-1n-1次合并，依次产生次合并，依次产生HTiHTi，i=n+1.2n-1i=n+1.2n-1：3.1)3.1)在在HT1.i-1HT1.i-1中选两个未被选过的中选两个未被选过的weightweight最小的两个结最小的两个结点点HTs1HTs1和和HTs2(HTs2(从从parent=0 parent=0 的结点中选的结点中选)3.2)3.2)修改修改HTs1HTs1和和HTs2HTs2的的parentparent值：值：parent=iparent=i 3.3)3.3)置置HTiHTi：weight=HTs1.weight+HTs2.weight,weight=HTs1.weight+HTs2.weight,lchlch=s1,=s1,rchrch=s2=s2霍夫曼树构造算法的实现霍夫曼树构造算法的实现算法算法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;weight parent lch ild rchild1155297814233110 0 0 0 0 0 0 00 0 0 0 0 0 0例例:设设n=8,w=5,29,7,8,14,23,3,11试设计试设计 huffman code(m=2*8-1=15)0 0 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0for(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;/s1,s2分别作为分别作为i的左右孩子的左右孩子 HTi.weight=HTs1.weight+HTs2.weight;/i 的权值为左右孩子权值之和的权值为左右孩子权值之和 weight parent lchild rchild115529781423311815192942581009 14101012139 111112131415150138562749101112140 0 0 0 0 0 0 00 0 0 0 0 0 0 013构造构造Huffman treeHuffman tree后后,HT,HT为为:void CreatHuffmanCode(HuffmanTree HT,HuffmanCode&HC,int n)/从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表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.lchild=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霍夫曼编码是霍夫曼编码是不等长编码不等长编码霍夫曼编码是霍夫曼编码是前缀编码前缀编码，即任一字符的编码都不，即任一字符的编码都不是另一字符编码的前缀是另一字符编码的前缀霍夫曼编码树中没有度为霍夫曼编码树中没有度为1 1的结点。若叶子结点的的结点。若叶子结点的个数为个数为n n，则霍夫曼编码树的，则霍夫曼编码树的结点总数为结点总数为 2n-12n-1发送过程：根据由发送过程：根据由霍夫曼树得到的编码表霍夫曼树得到的编码表送出字送出字符数据符数据接收过程：按接收过程：按左左0 0、右、右1 1的规定，从根结点走到一的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束直到接收数据结束霍夫曼编码的几点结论霍夫曼编码的几点结论1 1、定义和、定义和性质性质2 2、存储结构、存储结构3 3、遍历遍历4 4、线索化：线索树、线索化：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表树树二叉树二叉树森林森林中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码小结小结1.1.掌握二叉树的基本概念、掌握二叉树的基本概念、性质性质和存储结构和存储结构2.2.熟练掌握二叉树的熟练掌握二叉树的前、中、后序遍历方法前、中、后序遍历方法3.3.了解了解线索化线索化二叉树的思想二叉树的思想4.4.熟练掌握：熟练掌握：霍夫曼树霍夫曼树的实现方法、构造的实现方法、构造霍夫霍夫曼编码曼编码的方法的方法5.5.了解：森林与二叉树的转换，树的遍历方法了解：森林与二叉树的转换，树的遍历方法 小结小结