数据结构与算法Data Structure

《数据结构与算法Data Structure》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法DataStructureAlgorithms烟台南山学院信息科技学院数据结构与算法教学组16.4树和森林1.树和森林与二叉树的转换2.树和森林的存储方式3.树和森林的遍历21.树和森林与二叉树的转换转换步骤：step1:将树中同一结点的兄弟相连;step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转讨论1：树如何转为二叉树？3方法：加线—抹线—旋转abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点肯定没有右孩子！4讨论2：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变

2、为兄弟！abeidfhgc5法一：①各森林先各自转为二叉树；②依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）即F={T1,T2,…,Tm}B={root,LB,RB}6ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林转二叉树举例：（法二）兄弟相连长兄为父孩子靠左头根为根A7讨论4：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}82.

3、树和森林的存储方式树有三种常用存储方式：①双亲表示法②孩子表示法③孩子兄弟表示法1、用双亲表示法来存储思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。parentsdata结点结构dataparents1树结构23n9ABCGEIDHF缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例1:双亲表示法10思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一个混合结构。例如：abecdfhgdefghgfedcbah

4、123456782、用孩子表示法来存储bc11思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3、用孩子兄弟表示法来存储指向左孩子指向右兄弟12abecdfhgbacedfgh问：树转二叉树的“连线—抹线—旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。存储的过程就是转换的过程！例如：13先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历若森林为空，返回；中

5、序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历ABCDEFGHJI14路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍夫曼树：6.5Huffman树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacfg树中所有叶子结点的带权路径长度之和带权路径长度最小的树。a→e的路径长度＝树长度＝21015Huffman树简介：树的带权路径长度如何计算？WPL=wklkk=1nabdc752

6、4(a)cdab2457(b)bdac7524(c)经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：WPL最小的树。Huffman树WeightedPathLength16(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树

7、。③把新的二叉树加入F。构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径。先举例！17例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码。例如用二进制编码来实现。取d=00，i=01，a=10，n=11怎样实现Huffman编码？法2：不等长编码，例如用哈夫曼编码来实现。取d=0;i=10