树和二叉树作业answer.ppt

第6章 树和二叉树,作业解答,K,1 如图所示的二叉树的（a）画出其顺序存储和二叉链表存储。(b)列出该二叉树的叶子结点，指出该二叉树的深度(c)分别写出该二叉树的先序，中序，后序遍历序列。,作业1,2 编写一个算法统计二叉树中叶子结点的个数,3）已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。,1）将如图所示的二叉树进行中序线索化。,2 试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同,3 假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数,作业：2,作业：1,1）顺序存储：树的深度是7数组存储单元大小是27-1=127叶子结点L,FGM J,A,B,C,D,E,F,L,G,H,I,J,M,K,1,2,4,5,8,9,10,11,17,22,44,45,91,0 1 2 3 4 5 678 91011.91 126,A,B,0,E,C,0,0,K,F,G,D,J,.,0,0,遍历序列先序：ABEKLFCGDHMIJ中序 KLEFBGCMHIJDA后序 LKFEGMJIHDCBA,2统计出给定二叉树中叶子结点的数目（1）顺序存储结构的实现 int CountLeaf1（SqBiTree bt，int k）/*一维数组bt2k-1为二叉树存储结构，k为二叉树深度，函数值为叶子数。*/total=0;for(i=1;i(2k-1)/2)total+;return(total);,（2）二叉链表存储结构的实现 int CountLeaf2（BiTree bt）/*开始时，bt为根结点所在链结点的指针，返回值为bt的叶子数*/if(bt=NULL)return(0);if(bt-lchild=NULL,A,3)重建二叉树,作业：2,1,3,9,11,2,5,13,10,6,7,12,8,4,15,14,1）转化的二叉树如图,二叉树中序遍历序列：3 4 2 8 6 7 5 1 10 9 11 15 13 14 12,NULL,NULL,2 试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同解：（1）空二叉树或任一结点均无左子树的非空二叉树（2）空二叉树或任一结点均无右子树的非空二叉树（3）空二叉树或仅有一个结点的二叉树（4）空二叉树或仅有一个结点的二叉树,3 假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数,电文总码数:0100 1000000101 001 011 11 0001,注意:电文总编码形式不唯一,只要带权路径总长度为257的最优二叉树编码都是符合要求的.,解:先构造如图所示的最优二叉树:然后编码:,