《数据结构：第六章 树与二叉树》由会员分享，可在线阅读，更多相关《数据结构：第六章 树与二叉树（74页珍藏版）》请在金锄头文库上搜索。
1、六、树与二叉树六、树与二叉树6.1 6.1 树的定义树的定义数数据据结结构构线性结构：在数据结构中每个结点线性结构：在数据结构中每个结点都只有一个直接前驱或直接后继的都只有一个直接前驱或直接后继的结点。结点。非线性结构：在数据结构中至少存非线性结构：在数据结构中至少存在一个具有两个或两个以上直接前在一个具有两个或两个以上直接前驱或直接后继的结点。驱或直接后继的结点。六、树与二叉树六、树与二叉树6.1 6.1 树的定义树的定义 树（树（TreeTree）：）：由由n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。 n=0n=0的树称为的树称为空树空树； n0n0的的非空非空树树T
2、T（D D，R R）有：）有： (1) (1)有且仅有一个结点有且仅有一个结点rootroot没有前驱结点，结点没有前驱结点，结点rootroot称作树的根节点。称作树的根节点。 (2) (2)除根结点外，其余结点有且仅有一个前驱结点，除根结点外，其余结点有且仅有一个前驱结点，但可以有多个后继结点。但可以有多个后继结点。六、树与二叉树六、树与二叉树树的递归定义树的递归定义由由n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。n=0n=0的树称为的树称为空树空树；对对n0n0的树的树T T有：有： （1 1）有一个特殊的结点称为根结点，根）有一个特殊的结点称为根结点，根结点没有前驱
3、结点；结点没有前驱结点； （2 2）当）当n1n1时，除根结点外其他结点被分时，除根结点外其他结点被分成成m m（m0m0）个互不相交的集合）个互不相交的集合T T1 1,T,T2 2, ,T,Tm m。其。其中，每一个集合中，每一个集合T Ti i(1im(1im）本身又是一棵称）本身又是一棵称为根结点的子树的树。为根结点的子树的树。六、树与二叉树六、树与二叉树（空树）（空树）（a）A（b）（c）ABCDEFGHIKLMJ六、树与二叉树六、树与二叉树树的基本术语树的基本术语结点结点(Node):(Node):在树中通常把数据元素和在树中通常把数据元素和指向其指向其他节点的分支他节点的分支合起
4、来称作结点。合起来称作结点。结点的度结点的度(Degree)(Degree)：结点所拥有的子树的个结点所拥有的子树的个数或者后继结点数称为该结点的度。数或者后继结点数称为该结点的度。树的度：树的度：树中所有结点的度的最大值称为该树中所有结点的度的最大值称为该树的度。树的度。六、树与二叉树六、树与二叉树叶结点叶结点(leaf)(leaf)：度为度为0 0的结点称为叶结点，叶的结点称为叶结点，叶结点也称作终端结点。结点也称作终端结点。分支结点：分支结点：度不为度不为0 0的结点称为分支结点，分的结点称为分支结点，分支结点也称作非终端结点。（一棵树中除叶结支结点也称作非终端结点。（一棵树中除叶结点外
5、的所有结点都是分支结点）。点外的所有结点都是分支结点）。孩子结点孩子结点(Child)(Child)：树中一个结点的子树的根树中一个结点的子树的根结点或者树中一个结点的后继结点称作这个结结点或者树中一个结点的后继结点称作这个结点的孩子结点，也称作后继结点。点的孩子结点，也称作后继结点。双亲结点：双亲结点：若树中某结点有孩子结点，则该结若树中某结点有孩子结点，则该结点就称作他的孩子结点的双亲结点。点就称作他的孩子结点的双亲结点。六、树与二叉树六、树与二叉树子孙结点：子孙结点：某一结点的所有孩子结点，以及某一结点的所有孩子结点，以及这些孩子结点的孩子结点称为该结点子孙结这些孩子结点的孩子结点称为该
6、结点子孙结点。点。祖先结点：祖先结点：从根结点到树中某结点所经过的从根结点到树中某结点所经过的所有分支结点称为该结点的祖先结点。所有分支结点称为该结点的祖先结点。兄弟结点兄弟结点(Sibling)(Sibling)：具有相同的双亲结点的具有相同的双亲结点的结点互相称之为兄弟结点。结点互相称之为兄弟结点。六、树与二叉树六、树与二叉树结点的层次结点的层次(Level)(Level)：从根结点到树中某结点所经路从根结点到树中某结点所经路径上的分支数称为该结点的层次，其中根结点为第径上的分支数称为该结点的层次，其中根结点为第一层。一层。树的深度（树的深度（Depth)Depth)：树中所有结点的层次的
7、最大值树中所有结点的层次的最大值称为该树的深度，空树的深度规定为称为该树的深度，空树的深度规定为0 0。有序树：有序树：如果一棵树中任意一个结点的各个子树从如果一棵树中任意一个结点的各个子树从左到右都是有次序的。左到右都是有次序的。森林森林(Forest)(Forest)：是是m(m0)m(m0)棵互不相交的树的集合。棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。对树中每个结点而言，其子树的集合即为森林。六、树与二叉树六、树与二叉树6.2 6.2 二叉树二叉树6.2.1 6.2.1 二叉树的定义二叉树的定义二叉树二叉树(Binary Tree)(Binary Tree)：树的
8、度为树的度为2 2的有序树。的有序树。二叉树是二叉树是n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。n0n0的二叉树由一个根结点和两个互不相交的、分的二叉树由一个根结点和两个互不相交的、分别称作左子树和右子树的子二叉树构成。别称作左子树和右子树的子二叉树构成。六、树与二叉树六、树与二叉树二叉树的五种结点形态：二叉树的五种结点形态：空结点、无左右子树空结点、无左右子树结点、只有左子树结点、只有右子树结点和左结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。右子树均存在的结点。空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树
9、右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树六、树与二叉树六、树与二叉树6.2.1 6.2.1 二叉树的性质二叉树的性质性质性质3 3：对于一棵非空的二叉树，叶子结点数对于一棵非空的二叉树，叶子结点数n n0 0等等于度为于度为2 2的结点数的结点数n n2 2加加1 1，即，即n n0 0=n=n2 2+1;+1; 性质性质1 1：二叉树上第二叉树上第i i层上至多有层上至多有 （i1i1） 性质性质2 2：深度为深度为h h的二叉树至多有的二叉树至多有 个结点。个结点。六、树与二叉树六、树与二叉树满二叉树：满二叉树：在一棵二叉树中，
10、如果所有分支结点都在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称作满二叉树。层上，这样的二叉树称作满二叉树。A15234678910BCDEFGHIJKLM NO1112 13 14 15六、树与二叉树六、树与二叉树完全二叉树：完全二叉树：如果一棵树具有年如果一棵树具有年n n个结点的二叉树个结点的二叉树的结构与满二叉树的前的结构与满二叉树的前n n个结点的结构相同，这样个结点的结构相同，这样的二叉树称作完全二叉树。的二叉树称作完全二叉树。A15234678910BCDEFGHIJ六、树与二叉树六、
11、树与二叉树 性质性质4 4：具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度k k为为 。 性质性质5 5：对完全二叉树重编号为对完全二叉树重编号为i i的结点（的结点（1in1in，n1n1，n n为结点数）有：为结点数）有： 若若 ，即，即2in2in，则编号为，则编号为i i的结点的结点为分支结点，否则为叶子结点。为分支结点，否则为叶子结点。 若若i=0,i=0,是根，若是根，若i0i0，则它的双亲是，则它的双亲是 分支节点分支节点i i若存在左子女，则左子女是若存在左子女，则左子女是2*i+12*i+1， 若存在右子女，则右子女是若存在右子女，则右子女是2*i+2 2*i
12、+2 六、树与二叉树六、树与二叉树6.2.2 6.2.2 二叉树的存储结构二叉树的存储结构1.1.顺序存储结构：顺序存储结构：首先给二叉树各结点编号（与等首先给二叉树各结点编号（与等深度的完全二叉树中位置上的结点编号相同），然深度的完全二叉树中位置上的结点编号相同），然后按编号的顺序将各结点的值存放的数组中。后按编号的顺序将各结点的值存放的数组中。A B C D E F G H IJ K123456789101112131415顺序存储结构顺序存储结构六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树ABCDEFG1234679ABCD EF G 1 2 3 4 5 6 7 8 9 Ma
13、xSize-1 位置位置data六、树与二叉树六、树与二叉树6.2.2 6.2.2 二叉树的存储结构二叉树的存储结构2. 2. 链链表表存储结构：存储结构：链表中每个结点包含三个域，链表中每个结点包含三个域，一个数据域和两个指针域（分别指向对应结点的一个数据域和两个指针域（分别指向对应结点的左孩子和右孩子）。左孩子和右孩子）。六、树与二叉树六、树与二叉树BACDEFGABCDEFGroot具有具有n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针。个空指针。二叉树有一个表头指针，二叉树有一个表头指针，指向根节点指向根节点root。六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉
14、树6.3 6.3 二叉树的遍历二叉树的遍历树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次序访问次序访问树中所树中所有结点，使得每个结点被访问一次且仅被访问一次。有结点，使得每个结点被访问一次且仅被访问一次。 遍历的次序遍历的次序? ?树通常有前序遍历、中序遍历、后序遍历和层序遍树通常有前序遍历、中序遍历、后序遍历和层序遍历历4 4种方式。种方式。树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质? ?六、树与二叉树六、树与二叉树6.3.1 6.3.1 递归遍历二叉树递归遍历二叉树前序遍历前序遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回
15、；否则：否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序遍历遍历根根结点的右子树。结点的右子树。前序遍历序列：前序遍历序列：A B D G C E FA B D G C E FA AB BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树中序遍历中序遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。 中序遍历序列：中序遍历序列：D G B A E C FD G B A E C FA A
16、B BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树后序遍历后序遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；后序遍历序列：后序遍历序列：G D B E F C AG D B E F C AA AB BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树- - -/ /+ +* *abcdef二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：- + a * b - c
17、 d / e f中序遍历结果：中序遍历结果：a + b * c - d - e / f后序遍历结果：后序遍历结果：a b c d - * + e f / -六、树与二叉树六、树与二叉树若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为序列分别为ABCDEFGHI ABCDEFGHI 和和BCAEDGHFIBCAEDGHFI，如何构造该二如何构造该二叉树呢叉树呢? ? 六、树与二叉树六、树与二叉树前序
18、：前序：A B C D E F G H I中序：中序：B C A E D G H F I前序：前序：B C中序：中序：B C B C D EF GH IA前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI六、树与二叉树六、树与二叉树前序：前序：F G H I中序：中序：G H F I前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH六、树与二叉树六、树与二叉树1. 1. 根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；2. 2. 在中序序列中找到该元素，确定根结点的左右子在
19、中序序列中找到该元素，确定根结点的左右子树的中序序列；树的中序序列；3. 3. 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；4. 4. 由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5. 5. 由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 课后习题课后习题1.1.（5 5）、）、（6 6）中序）中序cbdeagihjfcbdeagihjf后序后序cebdijhgfa cebdijhgfa 已知一棵二叉树的前序序列和中序序列，构造该二叉已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：树的
20、过程如下： 六、树与二叉树六、树与二叉树6.3.2 6.3.2 应用二叉树遍历的实例应用二叉树遍历的实例为为了了建建立立一一棵棵二二叉叉树树，将将二二叉叉树树中中每每个个结结点点的的空空指指针针引引出出一一个个虚虚结结点点，其其值值为为一一特特定定值值如如“# #”，以以标标识识其其为为空空，把把这这样样处处理理后后的的二二叉叉树树称称为为原原二二叉叉树树的的扩展二叉树。扩展二叉树。 如何由一种遍历序列建立一棵二叉树？如何由一种遍历序列建立一棵二叉树？遍遍历历是是二二叉叉树树各各种种操操作作的的基基础础，可可以以在在遍遍历历的的过过程程中进行各种操作，例如建立一棵二叉树。中进行各种操作，例如建
21、立一棵二叉树。六、树与二叉树六、树与二叉树扩展二叉树前序遍历序列扩展二叉树前序遍历序列:A B # D # # C # #DBAC#DBAC#建立二叉树建立二叉树六、树与二叉树六、树与二叉树BACDEFGABCDEFGroot扩展二叉树前序遍历序列扩展二叉树前序遍历序列:ABD#EG#CF#六、树与二叉树六、树与二叉树设二叉树中的结点均为一个字符。设二叉树中的结点均为一个字符。假假设设扩扩展展二二叉叉树树的的前前序序遍遍历历序序列列由由键键盘盘输输入入，rootroot为为指向根结点的指针，二叉链表的建立过程是：指向根结点的指针，二叉链表的建立过程是：首首先先输输入入根根结结点点，若若输输入入
22、的的是是一一个个“# #”字字符符，则则表表明明该该二二叉叉树树为为空空树树，即即root=NULLroot=NULL；否否则则输输入入的的字字符符应应该该赋赋给给root-data,root-data,，之之后后依依次次递递归归建建立立它它的的左左子子树和右子树树和右子树 。六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树计算二叉树的节点个数计算二叉树的节点个数六、树与二叉树六、树与二叉树计算二叉树的高度计算二叉树的高度六、树与二叉树六、树与二叉树6.5 6.5 树与森林树与森林6.5.1 6.5.1 树的存储方式树的存储方式 2. 2.双亲双亲 表示法表示法 以一组连续的存储单元存
23、以一组连续的存储单元存 放节点，节点包括放节点，节点包括datadata域域 和和parentparent域，后者存放域，后者存放 双亲节点的指针。双亲节点的指针。ABCDEFG0123456ABCDEFG-1000113dataparent六、树与二叉树六、树与二叉树6.5.1 6.5.1 树的存储方式树的存储方式3.3.左左 子女子女右右 兄弟表示法兄弟表示法 又称为二叉树表示法，每个节点包括三个又称为二叉树表示法，每个节点包括三个域：域：datadata、firstChild(firstChild(存放第一个子女地址存放第一个子女地址) )nextSibling(nextSibling(
24、存放下一个兄弟地址存放下一个兄弟地址) )六、树与二叉树六、树与二叉树 1. 1.兄弟加线兄弟加线. .树转换为二叉树的步骤树转换为二叉树的步骤ABCDEFG六、树与二叉树六、树与二叉树2.2.保保留留双双亲亲与与第第一一孩孩子子连连线线, ,删删去去与与其他孩子的连线其他孩子的连线. .ABCDEFG 1. 1.兄弟加线兄弟加线. .树转换为二叉树的步骤树转换为二叉树的步骤六、树与二叉树六、树与二叉树3.3.顺顺时时针针转转动动, ,使使之层次分明之层次分明. .2.2.保保留留双双亲亲与与第第一一孩孩子子连连线线, ,删删去去与与其他孩子的连线其他孩子的连线. . 1. 1.兄弟加线兄弟加
25、线. .GDABECF树转换为二叉树的步骤树转换为二叉树的步骤六、树与二叉树六、树与二叉树CBEDFGAABEFCDG前序遍历前序遍历AEBCFDGABEFCDG前序遍历前序遍历树树的的前前序序遍遍历历等等价价于于二二叉叉树树的前序遍历！的前序遍历！六、树与二叉树六、树与二叉树EFBCGDA后序遍历后序遍历EFBCGDA中序遍历中序遍历树树的的后后序序遍遍历历等等价价于于二二叉叉树树的中序遍历！的中序遍历！CBEDFGAAEBCFDG六、树与二叉树六、树与二叉树6.5.2 6.5.2 森林与二叉树的转换森林与二叉树的转换 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二
26、叉树开始，依次把后一棵二叉树的从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。转换得到的二叉树。六、树与二叉树六、树与二叉树FEDCBAGH IKBAFEDCGH IKK IFEHABCGD六、树与二叉树六、树与二叉树 6.6 6.6 树的应用树的应用6.6.1 6.6.1 堆堆 堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都小于或：每个结点的值都小于或等于其左右孩子结点的值（称为等于
27、其左右孩子结点的值（称为小根堆小根堆），或每个结点的值都），或每个结点的值都大于或等于其左右孩子结点的值（称为大于或等于其左右孩子结点的值（称为大根堆大根堆）。）。 18 18 26 263535 60 6048487373 74 53 42 35 2036 25 18 22六、树与二叉树六、树与二叉树堆的存储结构堆的存储结构1.1.顺序存储结构顺序存储结构将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。 18 18 26 263535 60 6048487373六、树与二叉树六、树与二叉树性质：堆中性质：堆中0-n-10-n-1个结点编号中个结点编号中
28、0 0 -1 -1的为分支节点，的为分支节点， -n-1-n-1的节点为叶子节点的节点为叶子节点若若 , ,是根，若是根，若i0i0，则它的双亲是，则它的双亲是 分支节点分支节点i i若存在左子女，则左子女是若存在左子女，则左子女是2*i+12*i+1， 若存在右子女，则右子女是若存在右子女，则右子女是2*i+2 2*i+2 六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树 堆的建立、堆的建立、(2)(2)清除堆、清除堆、(3)(3)检查一个堆是否为空检查一个堆是否为空 堆的运算堆的运算六、树与二叉树六、树与二叉树 2626 48 483535 60 6050507373ij六、树与二
29、叉树六、树与二叉树 将新元素添加到堆尾，若新元素小于于双亲节将新元素添加到堆尾，若新元素小于于双亲节点，则需做调整：将双亲节点与新元素互换位置，点，则需做调整：将双亲节点与新元素互换位置，直至以新位置的双亲节点为根的子树仍为一个堆或直至以新位置的双亲节点为根的子树仍为一个堆或调整到堆顶为止；调整到堆顶为止； (4)(4)向堆中添加一个元素向堆中添加一个元素六、树与二叉树六、树与二叉树 18 18 26 263535 60 604848 73 73 1515 18 18 26 261515 60 60484873733535 1515 26 261818 60 60484873733535插入元
30、素插入元素1515，元素调整过程，元素调整过程六、树与二叉树六、树与二叉树算法的时间复杂度取决于算法的时间复杂度取决于whilewhile循循环次数，等于新元素到堆顶逐层上环次数，等于新元素到堆顶逐层上移的次数，为移的次数，为O(log2n)O(log2n)六、树与二叉树六、树与二叉树 7070 55 551717 5 5 42 42 46 4613139494六、树与二叉树六、树与二叉树 4646 55 551313 5 5 94 94 70 7017174242Currentsize/2-1六、树与二叉树六、树与二叉树 9494 70 701717 5 5 55 55 46 4613134
31、242Currentsize/2-1六、树与二叉树六、树与二叉树 9494 70 701717 5 5 55 55 46 461313 4242六、树与二叉树六、树与二叉树 7070 55 551717 5 5 42 42 46 461313 9494六、树与二叉树六、树与二叉树 4646 5 51717 55 55 42 42 13 137070 9494六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树 6.6 6.6 树的应用树的应用6.6.2 6.6.2 哈夫曼树与编码哈夫曼树与编码1.1.相关术语相关术语路径长度：路径长度：树中从一个节点到另外一个节点间分支构树中从一个节点到另
32、外一个节点间分支构成了路径，路径中分支条数。成了路径，路径中分支条数。 树的路径长度：树的路径长度：从树的根节点到树中各个节点的路从树的根节点到树中各个节点的路径长度之和。径长度之和。节点的带权路径长度：节点的带权路径长度：节点的路径长度与权的积节点的路径长度与权的积叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的数对叶子结点赋予的一个有意义的数值量。值量。 六、树与二叉树六、树与二叉树2.2.哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带结点，带权路径长度最小的二叉树。权路径长度最小的二叉树。例：给定例：给定4 4个叶子结点，其权值分别为个叶子结
33、点，其权值分别为11，3 3，4 4，66，可以构造出形状不同的多个二叉树。可以构造出形状不同的多个二叉树。 WPL=26 WPL=35 WPL=23 WPL=26 WPL=35 WPL=231 12 24 46 61 12 24 46 66 64 41 12 2六、树与二叉树六、树与二叉树哈夫曼树的特点：哈夫曼树的特点：1. 1. 权值越大的叶子结点越靠近根结点，而权值越小权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。的叶子结点越远离根结点。 2. 2. 只有度为只有度为0 0（叶子结点）和度为（叶子结点）和度为2 2（分支结点）的（分支结点）的结点，不存在度为结点，不存
34、在度为1 1的结点的结点. . WPL=26 WPL=35 WPL=23 WPL=26 WPL=35 WPL=231 12 24 46 61 12 24 46 66 64 41 12 2六、树与二叉树六、树与二叉树哈夫曼算法基本思想：哈夫曼算法基本思想： 初始化初始化：由给定的：由给定的n n个权值个权值 w w1 1，w w2 2，w wn n 构造构造n n棵只有一个根结点的二叉树，从而得到一个二叉树棵只有一个根结点的二叉树，从而得到一个二叉树集合集合F F T T1 1，T T2 2，T Tn n ； 选选取取与与合合并并：在在F F中中选选取取根根结结点点的的权权值值最最小小的的两两棵
35、棵二二叉叉树树分分别别作作为为左左、右右子子树树构构造造一一棵棵新新的的二二叉叉树树，这这棵棵新新二二叉叉树树的的根根结结点点的的权权值值为为其其左左、右右子子树树根根结结点的权值之和；点的权值之和； 删删除除与与加加入入：在在F F中中删删除除作作为为左左、右右子子树树的的两两棵棵二叉树，并将新建立的二叉树加入到二叉树，并将新建立的二叉树加入到F F中；中； 重复重复、两步，当集合两步，当集合F F中只剩下一棵二叉树中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。时，这棵二叉树便是哈夫曼树。 六、树与二叉树六、树与二叉树第第1 1步：初始化步：初始化W W22，4 4，5 5 ，3 3 哈夫曼
36、树的构造过程哈夫曼树的构造过程3524第第2 2步：选取与合并步：选取与合并32 5第第3 3步：删除与加入步：删除与加入5432 5六、树与二叉树六、树与二叉树W W22，4 4，5 5 ，3 3 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2 2步步5 54 43 32 2 5 55 54 4 9 9重复第重复第3 3步步 5 55 54 4 9 93 32 2六、树与二叉树六、树与二叉树W W22，3 3，4 4，5 5 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2 2步步重复第重复第3 3步步 554 932 554 93214六、树与二叉树六、树与二叉树3.3.哈夫曼树编码
37、哈夫曼树编码p 编编码码：给给每每一一个个对对象象标标记记一一个个二二进进制制位位串串来来表表示一组对象。例：示一组对象。例：ASCIIASCII，指令系统，指令系统p 等等长长编编码码：表表示示一一组组对对象象的的二二进进制制位位串串的的长长度度相等。相等。p 不不等等长长编编码码：表表示示一一组组对对象象的的二二进进制制位位串串的的长长度不相等。度不相等。不等长编码如何设计唯一性？不等长编码如何设计唯一性？六、树与二叉树六、树与二叉树p 前前缀缀编编码码：一一组组编编码码中中任任一一编编码码都都不不是是其其它它任任何何一个编码的前缀一个编码的前缀 。p 前缀编码保证了在解码时不会有多种可能。前缀编码保证了在解码时不会有多种可能。 哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码六、树与二叉树六、树与二叉树9523 5 10 1911 2687 15 45编码方案：编码方案：A A：0000B B：1010C C：010010D D：110110E E：111111F F：01100110G G：01110111例例：一一组组字字符符A, A, B, B, C, C, D, D, E, E, F, F, GG出出现现的的频频率率分分别别是是9, 11, 5, 7, 8, 2, 39, 11, 5, 7, 8, 2, 3，设计最经济的编码方案。，设计最经济的编码方案。
