23490数据结构习题答案 下载本文

(17) (11) 7 10 6 (5) 2 3

方案比较: 字母对应出现字母对应出现 编号 编码 频率 编号 编码 频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 4 1110 0.06 4 011 0.06 10 0.32 5 100 0.32 5 6 101 0.03 方案1的WPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论:哈夫曼编码优于等长二进制编码

(4)已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT的存储结构的初态和终态。

初态:

weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0

10 0 0 0

11 0 0 0

12 0 0 0

13 0 0 0

weight parent lchild rchild

1 2 3 4 5 6 7 8 9 10 11 12 13 3 12 7 4 2 8 11 5 9 15 20 27 47 8 12 10 9 8 10 11 9 11 12 13 13 0 0 0 0 0 0 0 0 5 4 3 9 2 11 0 0 0 0 0 0 0 1 8 6 7 10 12 终态

3.算法设计题

以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。 int LeafNodeCount(BiTree T) {

if(T==NULL)

return 0; //如果是空树,则叶子结点个数为0

else if(T->lchild==NULL&&T->rchild==NULL)

return 1; //判断该结点是否是叶子结点(左孩子右孩子都为空),若是则返回1

else

return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); }

(2)判别两棵树是否相等。

(3)交换二叉树每个结点的左孩子和右孩子。 void ChangeLR(BiTree &T) { BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp;

} ChangeLR(T->lchild); ChangeLR(T->rchild); }

(4)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。

void DoubleTraverse(BiTree T) {

if(T == NULL) return;

else if(T->lchild==NULL&&T->rchild==NULL) cout<data; else {

cout<data;

DoubleTraverse(T->lchild); cout<data;

DoubleTraverse(T->rchild); } }

(5)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。 int Width(BiTree bt)//求二叉树bt的最大宽度

{if (bt==null) return (0); //空二叉树宽度为0 else

{BiTree Q[];//Q是队列,元素为二叉树结点指针,容量足够大

front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置

temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)

{p=Q[front++]; temp++; //同层元素数加1

if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束, {last=rear;

if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while

return (maxw);

}//结束width

(6)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。 int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数

if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p->data); //出队,访问结点

if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为

1的结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } }//if(bt)

return(num); }//返回度为1的结点的个数

(7)求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。 [题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树结点指针,l中保留当前最长路径中的结点

int i,top=0,tag[],longest=0; while(p || top>0)

{ while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看路径长度

if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈,记住最高栈顶指针,退栈 }

else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath

(8)输出二叉树中从每个叶子结点到根结点的路径。

[题目分析]采用先序遍历的递归方法,当找到叶子结点*b时,由于*b叶子结点尚未添加到path中,因此在输出路径时还需输出b->data值。对应的递归算法如下: void AllPath(BTNode *b,ElemType path[],int pathlen) {

int i;

if (b!=NULL) {

if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点 {

cout << \到根结点路径:\ for (i=pathlen-1;i>=0;i--) cout << endl; } else {

path[pathlen]=b->data; //将当前结点放入路径中 pathlen++; //路径长度增1 AllPath(b->lchild,path,pathlen); //递归扫描左子树 AllPath(b->rchild,path,pathlen); //递归扫描右子树 pathlen--; //恢复环境 } } }