数据结构数据结构第六章第六章(下下)数据结构数据结构tjm静态双亲链表的类型定义参见静态双亲链表的类型定义参见P135P1356.4 树和森林树和森林 6.4.1 6.4.1 树的存储结构树的存储结构树的存储结构树的存储结构双亲表示法双亲表示法双亲表示法双亲表示法实现：定义数组存放树的结点，每个结点含两个域：实现：定义数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息。数据域：存放结点本身信息。双亲域：指示本结点的双亲结点在数组中的位置。双亲域：指示本结点的双亲结点在数组中的位置。特点：找双亲容易，找孩子难。特点：找双亲容易，找孩子难。数据结构数据结构tjmabcdefhgi101124440acdefghibdataparent501234678数据结构数据结构tjmabcdefhgi 1 2 3 4 8 6 7 5501234678acdefghib data fc孩子链表表示法孩子链表表示法孩子链表表示法孩子链表表示法（类型定义参见类型定义参见P136P136）每个结点的孩子结点用单链表存储，再用含每个结点的孩子结点用单链表存储，再用含n n个元个元素的数组指向每个孩子链表。素的数组指向每个孩子链表。数据结构数据结构tjm501234678acdefghibdatafc 1 2 3 4 8 6 7 5101124440parentabcdefhgi带双亲的孩子链表带双亲的孩子链表带双亲的孩子链表带双亲的孩子链表数据结构数据结构tjmabcdefhgi a b c d e f g h i孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）实现：用二叉链表作树的存储实现：用二叉链表作树的存储结构，链表中每个结点的两个结构，链表中每个结点的两个指针域分别指向其第一个孩子指针域分别指向其第一个孩子结点和下一个兄弟结点。结点和下一个兄弟结点。数据结构数据结构tjmACBED树树ABCDE二叉树二叉树 A B C D E A B C D E 6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换森林与二叉树的转换森林与二叉树的转换 A B C D E 数据结构数据结构tjmABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空。树转换成的二叉树其右子树一定为空。加线：在兄弟之间加一连线。加线：在兄弟之间加一连线。抹线：对每个结点，除了其左孩子外，抹掉其与抹线：对每个结点，除了其左孩子外，抹掉其与其余孩子之间的连线。其余孩子之间的连线。旋转：将树作适当的旋转即可。旋转：将树作适当的旋转即可。 将树转换成二叉树将树转换成二叉树将树转换成二叉树将树转换成二叉树数据结构数据结构tjmABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI将将将将二叉二叉二叉二叉树转换成树树转换成树树转换成树树转换成树加线：若某加线：若某结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将该结点该结点的右孩子，右孩子的右孩子，的右孩子，右孩子的右孩子，沿分支找到的所沿分支找到的所有右孩子，都与有右孩子，都与该结点该结点的双亲用线连起来。的双亲用线连起来。抹线：抹掉原二叉树中双亲与右孩子之间的连线。抹线：抹掉原二叉树中双亲与右孩子之间的连线。调整：将结点按层次排列，形成树结构。调整：将结点按层次排列，形成树结构。数据结构数据结构tjmABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林转换成二叉树森林转换成二叉树森林转换成二叉树森林转换成二叉树将各棵树分别转换成二叉树。将各棵树分别转换成二叉树。将每棵树的根结点用线相连。将每棵树的根结点用线相连。以第一棵树根结点为二叉树的根，再以根结点为以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。轴心，顺时针旋转，构成二叉树型结构。数据结构数据结构tjmABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林二叉树转换成森林二叉树转换成森林二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。成孤立的二叉树。还原：将孤立的二叉树还原成树。还原：将孤立的二叉树还原成树。数据结构数据结构tjm 6.4.3 6.4.3 树的遍历树的遍历树的遍历树的遍历（1 1）树的先根遍历）树的先根遍历 树的后根遍历树的后根遍历（2 2）森林的先序遍历）森林的先序遍历 森林的中序遍历森林的中序遍历若给定树的先根和后根序列则可唯一地确定一棵树。若给定树的先根和后根序列则可唯一地确定一棵树。数据结构数据结构tjm6.6 哈夫曼树及其应用哈夫曼树及其应用 6.6.1 6.6.1 最优二叉树（哈夫曼树）最优二叉树（哈夫曼树）最优二叉树（哈夫曼树）最优二叉树（哈夫曼树）从树中一个结点到另一个结点之间的分支构成这从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。两个结点间的路径。路径长度：路径上的分支数。路径长度：路径上的分支数。树的路径长度：从树根到每个结点的路径长度之树的路径长度：从树根到每个结点的路径长度之和。和。结点的带权路径长度：从该结点到树根之间的路结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。径长度与结点上权的乘积。数据结构数据结构tjm树的带权路径长度：树中所有叶子结点的树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：带权路径长度之和。记作：设有设有n n个权值个权值 w w1 1,w,w2 2,w wn n ，构造一棵有构造一棵有n n个叶个叶子结点的二叉树，第子结点的二叉树，第i i个叶子的权值为个叶子的权值为w wi i, ,则则wplwpl最小的二叉树叫最小的二叉树叫最优二叉树（哈夫曼树）最优二叉树（哈夫曼树）, ,即即带权路径长度最短的树带权路径长度最短的树。数据结构数据结构tjm例例: 有有4个结点，权值分别为个结点，权值分别为7，5，2，4，构造有，构造有4个叶子结点的二叉树。个叶子结点的二叉树。dcab2475WPL=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数据结构数据结构tjm等级等级分数段分数段比例比例ABCDE059 6069 70798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNAEADBCa80a70a60a90EYNDYNCYNBYNA例：例：70 a80a60CYNBYNDYNEYNA80 a9060 a70比较比较20500次次比较比较22000次次比较比较31500次次假设输入假设输入1000010000个数个数数据结构数据结构tjmHuffmanHuffmanHuffmanHuffman树的树的树的树的构造构造构造构造构造构造HuffmanHuffman树步骤：树步骤：根据给定的根据给定的n n个权值个权值 w w1 1,w,w2 2,w wn n ，构造构造n n棵只有棵只有根结点的二叉树根结点的二叉树。在森林中选取两棵根结点权值最小的树作左右子在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树在森林中删除这两棵树，同时将新得到的二叉树加入森林中。加入森林中。重复上述两步，直到只含一棵树为止，这棵树即重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。哈夫曼树。数据结构数据结构tjm例：例：a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4数据结构数据结构tjm例：例：w=5, 29, 7, 8, 14, 23, 3, 1151429 7 823 3 111429 7 823 11358871514292335811113519142923871511351929 2314872929148729113523421135234229148758113523291487100113523291487数据结构数据结构tjmlch weight rch parent1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0lch weight rch parent1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0is1=3,s2=4一棵有一棵有n个叶子结点的个叶子结点的Huffman树有树有2n-1个结点，采用个结点，采用顺序存储结构顺序存储结构一维结构数组一维结构数组。Huffman算法实现：算法实现：算法算法参见参见P147P147算法算法6.126.12。例：例：a7b5c2d4数据结构数据结构tjmlch weight rch parent1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0is1=2,s2=5lch weight rch parent1 2 3 4 5 6 70 0 0 0 3 2 17 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0is1=1,s2=61234000111111数据结构数据结构tjm例：要传输的字符集例：要传输的字符集 D=C,A,S,T, ; D=C,A,S,T, ; ，字符出字符出现频率现频率 w=2,4,2,3,3w=2,4,2,3,3CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111 6.6.2 6.6.2 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码编码：编码：根据字符出现频率构造根据字符出现频率构造HuffmanHuffman树，然后将树，然后将树中结点引向其左孩子的分支标树中结点引向其左孩子的分支标“0”“0”，引向其右，引向其右孩子的分支标孩子的分支标“1”“1”；每个字符的编码即为从根到；每个字符的编码即为从根到每个叶子的路径上得到的每个叶子的路径上得到的0 0、1 1序列。序列。如：电文是如：电文是CAS;CAT;SAT;ATCAS;CAT;SAT;AT其编码是其编码是 “ “11010111011101000011111000011000”11010111011101000011111000011000”数据结构数据结构tjm如如: : 电文为电文为“1101000”1101000” 译文只能是译文只能是“CAT”CAT”CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111译码：译码：从从HuffmanHuffman树根开始，从待译码电文中逐位树根开始，从待译码电文中逐位取码。若编码是取码。若编码是“0”“0”，则向左走；若编码是，则向左走；若编码是“1”“1”，则向右走，一旦到达叶子结点，则译出一个字符；，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。再重新从根出发，直到电文结束。