资源描述：
《树和二叉树作业answer.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章树和二叉树作业解答KABCDEFLGHIJM1如图所示的二叉树的（a）画出其顺序存储和二叉链表存储。(b)列出该二叉树的叶子结点，指出该二叉树的深度(c)分别写出该二叉树的先序，中序，后序遍历序列。作业12编写一个算法统计二叉树中叶子结点的个数3）已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。1）将如图所示的二叉树进行中序线索化。2试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同3假定用于
2、通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数作业：2139112513106712841514作业：11）顺序存储：树的深度是7数组存储单元大小是27-1=127叶子结点L,FGMJABCDEFLGHIJMK124589101117224445910123456…7……89…10…11….…91126AB0EC00KFGDJ……..H^L^^M^^IABECDGKFJ^^^^^^^^^00遍历序列先序：A
3、BEKLFCGDHMIJ中序KLEFBGCMHIJDA后序LKFEGMJIHDCBA2．统计出给定二叉树中叶子结点的数目（1）顺序存储结构的实现intCountLeaf1（SqBiTreebt，intk）{/*一维数组bt[2k-1]为二叉树存储结构，k为二叉树深度，函数值为叶子数。*/total=0;for(i=1;i<=2k-1;i++){if(bt[i]!=0){if((bt[2i]==0&&bt[2i+1]==0)
4、
5、(i>(2k-1)/2))total++;}}return(total);}（2）二叉链表存储结构的实现intCountLeaf2（BiTre
6、ebt）{/*开始时，bt为根结点所在链结点的指针，返回值为bt的叶子数*/if(bt==NULL)return(0);if(bt->lchild==NULL&&bt->rchild==NULL)return(1);return(CountLeaf2(bt->lchild)+CountLeaf2(bt->rchild));}ABFGECDHIJ3)重建二叉树作业：21391125131067128415141）转化的二叉树如图二叉树中序遍历序列：342867511091115131412NULLNULL2试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相
7、同；（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编码,并给出该电文的总码数C7:366122C2:251711C5:107C8:4C3:339C1:5C4:6C6:
8、1110000001101110110C1:0100C2:10C3:0000C40101C5001C6011C711C80001电文总码数:01001000000101001011110001注意:电文总编码形式不唯一,只要带权路径总长度为257的最优二叉树编码都是符合要求的.解:先构造如图所示的最优二叉树:然后编码:
