数据结构ch4作业

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中序：BDECAGIJHF解：4.12已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。先序：ABCDEFGHIJ中序：CBEDAHGFIJ后序：CEDBHGJIFAABCDEFGHIABCDEFGHIJ①对应二叉树②对应二叉树ABCDEFGHIJ24.17设计算法以输出每个结点到根结点之间的路径上的所有结点的值。解：算法如下：//先序遍历查找结点x，打印到根节点路径voidBiTreeSearchNR(BiNode*pBT,elementTypex,BiNode*&pR){BiNode*p;seqStackS;inttag[MaxLen];//标记左子树、右子树initStack(S);//初始化栈p=pBT;while(p||!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);coutp-data,;}break;//退出循环}elsep=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直接弹出3{popStack(S,p);p=NULL;//上面出栈的p已经没有，回去循环取栈顶的下一个元素}}}}4.24将下图中的森林转换为对应的二叉树。○A○J○K○O○B○E○G○L○N○P○C○D○F○H○I○M解：转换后的二叉树如下图○A○B○J○C○E○K○D○F○G○L○O○H○M○N○P○I4.28将下图中的二叉树转换为对应的森林。○A○B○C○D○E○F○G○H○I○J○K○L○M○N○O4○A○C○G○O○B○E○K○F○M○N○D○I○J○L○H4.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=3514.35已知一个文件中仅有10个不同的字符，各字符出现的个数分别为100,150,180,200,260,300,350,390,400,500。试对这些符号重新编码，以压缩文件的规模，并461012222244115711518338101820385求出其压缩后的规模以及压缩比（压缩前后的规模比）。解：采用哈夫曼编码，根据题意得到如下哈夫曼树和哈夫曼编码。等长编码：若采用等长编码，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+390+400+500)=9120压缩比=9120/11320=80.6%167011602501501005102606503503003802001807703909005004002830