数据结构ch4作业

1、15个结点仅有右孩子，度节点数 n1，2度节点数 n2。n1=10+15=25 A B G C F D E A B F D J H - F 15个结点仅有右孩子，度节点数 n1，2度节点数 n2。n1=10+15=25 A B G C F D E A B F D J H - F G H I G I 第四章习题4.3 如果已知一棵二叉树有 20个叶子结点，有 10个结点仅有左孩子，求出该二叉树的结点数目。解：设结点总数为 n，叶子数 n0，1由题意得： n0=20 有由二叉树性质得： n2=n0-1=20-1=19 所以，总结点数 n= n0+ n1+ n2=20+25+19=64 4.10证明

2、：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：先序： ABCDEFGHI 先序： ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 解：A B C H D I E 对应二叉树J 对应二叉树4.12已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。先序： A B C D E F G H I J 中序： C B E D A H G F I J后序： C ED B H G J I F AC 4.17设计算法以输出每个结点到根结点之间的路径上的所有结点的值。E 解：算法如下：/先序遍历查找结点

3、 x，打印到根节点路径void BiTreeSearchNR(BiNode* pBT, elementType x, BiNode* &pR) -完整版学习资料分享- -WORD 格式-可编辑-专业资料- - BiNode* p; seqStack S; int tagMaxLen; /标记左子树、右子树initStack(S); /初始化栈p=pBT; while(p | !stackEmpty(S) if(p) /p!=NULL pushStack(S, p); /当前根节点指针 p 入栈tagS.top=0; /标记遍历左子树/判定 p是否目标结点if(p-data=x) /返回 p指针

4、pR=p; while(!stackEmpty(S) /找到目标结点，打印到根节点的路径 popStack(S,p); coutdatalChild; /遍历左子树 else /p=NULL 但是栈不空 stackTop(S, p); /取栈顶，但不退栈，以便遍历 p的右子树if(tagS.top=0) / 说明 p 的右子树尚未遍历，设置标记，遍历右子树 tagS.top=1; p=p-rChild; else /tagS.top=1 ，说明栈顶结点 p的左右子树都已经遍历， 且没有找到目标，p直接弹出 popStack(S, p); p=NULL; /上面出栈的 p已经没有，回去循环取栈顶

5、的下一个元素 4.24 将下图中的森林转换为对应的二叉树。-完整版学习资料分享JEDJEGMCEICEI- KGFKLNFJGKJOLHOPGKOFLNILMPMMNNO-WORD 格式-可编辑-专业资料- JEDJEGMCEICEI- KGFKLNFJGKJOLHOPGKOFLNILMPMMNNOABC解：转换后的二叉树如下图ABCD FHI4.28将下图中的二叉树转换为对应的森林。ABDHABDH4.34 以数据集合 4,6,8,10,12,15,18,20,22 中的元素为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度。解：WPL=115+44+71+22+33+38+10+18=

6、351 -完整版学习资料分享71 22 12 6 - 33 15 8 38 18 10 18 20 -WORD 格式-可编辑-专业资料- 71 22 12 6 - 33 15 8 38 18 10 18 20 =4*(4+6+8+10)+3*(12+15+18+20)+2*22=351 115 44 22 10 4 4.35 已 知 一 个 文 件 中 仅 有 10 个 不 同 的 字 符 ， 各 字 符 出 现 的 个 数 分 别 为100,150,180,200,260,300,350,390,400,500。试对这些符号重新编码， 以压缩文件的规模， 并求出其压缩后的规模以及压缩比（压缩

7、前后的规模比） 。解：采用哈夫曼编码，根据题意得到如下哈夫曼树和哈夫曼编码。等长编码：若采用等长编码， 10个不同字符需要 4位编码，则总码长度 =4*(100+150+180+200+260+300+350+390+400+500)=11320 Haffman 编码，码长 =WPL WPL=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% -完整版学习资料分享1670 650 260 150 - 770 300 180 900 350 200 380 390 400 50