数据结构ch4作业.doc

《数据结构ch4作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章习题4.3如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。解：设结点总数为n，叶子数n0，1度节点数n1，2度节点数n2。由题意得：n0=20n1=10+15=25有由二叉树性质得：n2=n0-1=20-1=19所以，总结点数n=n0+n1+n2=20+25+19=644.10证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：①先序：ABCDEFGHI②先序：ABCDEFGHIJ中序：ADECFBGIH中序：BDECA

2、GIJHF解：ABCDEFGHIABCDEFGHIJ①对应二叉树②对应二叉树ABCDEFGHIJ4.12已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。先序：ABCDEFGHIJ中序：CBEDAHGFIJ后序：CEDBHGJIFA4.17设计算法以输出每个结点到根结点之间的路径上的所有结点的值。解：算法如下：//先序遍历查找结点x，打印到根节点路径voidBiTreeSearchNR(BiNode*pBT,elementTypex,BiNode*&pR){BiNode*p;seqStackS

3、;inttag[MaxLen];//标记左子树、右子树initStack(S);//初始化栈p=pBT;while(p

4、

5、!stackEmpty(S)){if(p)//p!=NULL{pushStack(S,p);//当前根节点指针p入栈tag[S.top]=0;//标记遍历左子树//判定p是否目标结点if(p->data==x){//返回p指针pR=p;while(!stackEmpty(S))//找到目标结点，打印到根节点的路径{popStack(S,p);cout<data<<",";}break;//退出循环}e

6、lsep=p->lChild;//遍历左子树}else//p==NULL但是栈不空{stackTop(S,p);//取栈顶，但不退栈，以便遍历p的右子树if(tag[S.top]==0)//说明p的右子树尚未遍历，设置标记，遍历右子树{tag[S.top]=1;p=p->rChild;}else//tag[S.top]==1，说明栈顶结点p的左右子树都已经遍历，且没有找到目标，p直接弹出{popStack(S,p);p=NULL;//上面出栈的p已经没有，回去循环取栈顶的下一个元素}}}}4.24将下图中的森林转换为对应的二叉树

7、。解：转换后的二叉树如下图4.28将下图中的二叉树转换为对应的森林。4.34以数据集合{4,6,8,10,12,15,18,20,22}中的元素为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度。解：WPL=115+44+71+22+33+38+10+18=351=4*(4+6+8+10)+3*(12+15+18+20)+2*22=351461012222244115711518338101820384.35已知一个文件中仅有10个不同的字符，各字符出现的个数分别为100,150,180,200,260,300,350,39

8、0,400,500。试对这些符号重新编码，以压缩文件的规模，并求出其压缩后的规模以及压缩比（压缩前后的规模比）。解：采用哈夫曼编码，根据题意得到如下哈夫曼树和哈夫曼编码。等长编码：若采用等长编码，10个不同字符需要4位编码，则总码长度=4*(100+150+180+200+260+300+350+390+400+500)=11320Haffman编码，码长=WPLWPL=2830+1160+1670+510+650+770+900+250+380=9120=4*(100+150+180+200)+3*(260+300+350+3

9、90+400+500)=9120压缩比=9120/11320=80.6%167011602501501005102606503503003802001807703909005004002830