《二叉树数据结构复习》由会员分享，可在线阅读，更多相关《二叉树数据结构复习（19页珍藏版）》请在金锄头文库上搜索。
1、二叉树复习题算法与数据结构算法与数据结构1.给定二叉树的两种遍历序列，分别是：给定二叉树的两种遍历序列，分别是：(1)已知一棵二叉树的先序序列和中序序列分别为已知一棵二叉树的先序序列和中序序列分别为ABDGHCEFI和和GDHBAECIF，请画出此二叉树。，请画出此二叉树。(2)已知一棵二叉树的中序序列和后序序列分别为已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和和DECBHGFA，请画出此二叉树。，请画出此二叉树。答案答案2.试写出如图所示的二叉树分别按先序、中序、后试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。序遍历时得到的结点序列。答案答案3.假设用于通信
2、的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.(1)为这8个字母设计哈夫曼编码。(2)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?答案答案4.对于如图所示的有向图，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；答案答案5.假设图的顶点是A,B.，请根据下述的邻接矩阵画出相应的无向图或有向图。(a)(b)答案答案6.对下图
3、所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。答案答案7.对下图所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径。答案答案8.用弗洛伊德算法求下图所示的有向图的所有顶点之间的最短路径。写出二维数组和路径在执行该算法的过程中各步的状态。答案答案1.解：解：(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点：/(2)以同样的方法可画出该二叉树：/ABCDEF
4、G HIABFCGDHE2.解：解：(a)前序序列：12345中序序列：24531后序序列：54321(b)前序序列：12345中序序列：13542后序序列：54321(c)前序序列：12357864中序序列：17583524后序序列：78563421(d)前序序列：124735689中序序列：742153896后序序列：7425896313.解：解：(1)哈夫曼编码接下页根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000(2)用三位二进制数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.
5、02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.612.61/3=0.87=87%其平均码长是等长码的87%。所以平均压缩率为13%。4.【解答】(1)以顶点为根的深度优先生成树（不唯一）：5.答答:6.7.解：循环状态表如下：循环集合KD1D2D3D4D5D6初始化1-0201511,33019152521,3,2201915292531,3,2,660191529292541,3,2,6,440191529292551,3,2,6,4,55019152929256同上-同上从源点1到各点的路径如下所示：1到2：1321到3：131到4：13641到5：13251到6：1368.解：例ACB2643110 4 116 0 23 0初始：路径：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入V1：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路径：AB ABCBCA BCCA CAB
