《树和二叉树作业a》PPT课件

《树和二叉树作业a》PPT课件

ID:38927798

大小:302.32 KB

页数:10页

时间:2019-06-21

《树和二叉树作业a》PPT课件_第1页
《树和二叉树作业a》PPT课件_第2页
《树和二叉树作业a》PPT课件_第3页
《树和二叉树作业a》PPT课件_第4页
《树和二叉树作业a》PPT课件_第5页
资源描述:

《《树和二叉树作业a》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遍历序列先序:ABEKLFCGDHM

3、IJ中序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(BiTreebt){/*开始时,bt为根

6、结点所在链结点的指针,返回值为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)前序序列和中序序列相同;(2)中序序列和后序序列相同;(3)

7、前序序列和后序序列相同;(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:1110000001101110110C1:010

8、0C2:10C3:0000C40101C5001C6011C711C80001电文总码数:01001000000101001011110001注意:电文总编码形式不唯一,只要带权路径总长度为257的最优二叉树编码都是符合要求的.解:先构造如图所示的最优二叉树:然后编码:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。