发布时间 : 星期三 文章《数据结构与算法》课后习题答案更新完毕开始阅读013ada85e53a580216fcfe29
（1）哈夫曼树：
a：10 b：110 c：010 d：1110 e：011 f：00 g：1111
（2）对这7个字母进行等长编码，至少需要3位二进制数。
等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3 哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54 哈夫曼编码比等长编码使电文总长压缩了：1 - 2.54/3=15.33%
5.3.4 算法设计题
1．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。
【提示】采用递归算法实现。
int count(BiTree root)
{ if (root==NULL) return (0); else
return (count(root->lchild)+count(root->rchild)+1);
} 2．请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点的rchild域存放链指针。
【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkList head,pre=NULL; /*全局变量*/ LinkList InOrder(BiTree T)
/*中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头指针为head*/ { if(T) { InOrder(T->lchild);
if (T->lchild==NULL && T->rchild==NULL) if (pre==NULL) { head=T; pre=T; } else { pre->rchild=T;
pre=T; }
InOrder(T->rchild);
/*中序遍历左子树*/ /*当前是叶子结点*/
0
二叉树结点的数目＝
当二叉树为空
左子树结点数目＋右子树结点数目＋1 当二叉树非空
/*处理第一个叶子结点*/ /*将叶子结点链入链表*/ /*中序遍历右子树*/
pre->rchild=NULL; return(head); }
/*设置链表尾结点*/
3．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树的深度的算法。
【提示】采取递归算法。
int Height(BiTree root) { int hl,hr;
if (root==NULL) return(0); else { hl=Height(root->lchild);
hr=Height(root->rchild); if (hl>hr) return (hl+1); else return(hr+1); }
}
4．给定一棵用二叉链表表示的二叉树，其根指针为root，试求二叉树各结点的层数。 【提示】采用先序递归遍历算法实现。
二叉树结点的层次数＝
1
当结点为根结点 当结点非根结点
其双亲结点的层次数＋1
void fun (BiTree root, int n) { if (t==NULL) return;
else{ printf(―%d‖,n);
fun(root->lchild,n+1); fun(root->rchild,n+1);
}
}
5．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。
【提示】设root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。
void Exchange(BiTree root) { BiTNode *p;
if (root)
{ Exchange(root->lchild);
Exchange(root->rchild); p=root->lchild;
root->lchild=root->rchild;
root->rchild=p; }
}
6．一棵具有n个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先序遍历。
【提示】二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储结构的二叉树进行先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储结构下，判二叉树结点为空的条件为：结点下标大于n，或结点值为0（一般二叉树中的“虚结点”）。 void PreOrder (datatype data[n+1]) /*0号单元未用*/ { int stack[n] ; int top; if(n<1) return; t=1; top=0;
while (t<=n||top>0)
{ while (t<=n&&data[t]!=0)
{ Visite(data[t]);
stack[top]=t; top++; t=t*2; }
if (top<=0) return;
else { top--; t=stack[top]; t=t*2+1; } }
7．二叉树中查找值为x的结点，试设计打印值为x 的结点的所有祖先结点算法。 【提示】对二叉树进行先序非递归遍历，查找值为x的结点。进入子树时，将子树的根压栈；从子树返回时，将栈顶元素出栈。当找到值为x的结点时，栈中存放的就是其祖先结点，依次打印各结点的值。
void PrintNode (BiTree T, datatype x)
{ Init_Stack(S); /*初始化空栈*/ p=T;
while (p|| !Empty_Stack(S)) /*若p非空，或栈非空*/ { while (p)
{ if (p->data==x) /*若当前结点值为x，依次输出栈中元素的值*/
{ while (!Empty_Stack(S)) { Pop(S,q);
printf(q->data); } return;
}
else{ Push_Stack(S,p);} /*若当前结点值不是x，压栈*/
p=p->lchild; }
if(!Empty_Stack(S))
{ Pop_Stack(S,r); /*当栈非空，栈顶元素出栈，进入右子树*/
p=r->rchild; } else return; }
}
}
8．已知一棵二叉树的后序遍历序列和中序遍历序列，写出可以确定这棵二叉树的算法。 【提示】根据后序遍历和中序遍历的特点，采用递归算法实现。 void InPost (char in [ ] , char post [ ] , int il , int ir, int pl, int pr, BiTree t)
/*数组in和数组post中存放着二叉树的中序遍历序列和后序遍历序列，il和ir表示中序遍历序列的左右端*/
/*点， pl和 pr表示后序遍历序列的左右端点，t表示二叉树的根*/
{ t=(BiTNode *) malloc(sizeof(BiTNode)); }
9．编写算法判断一棵二叉链表表示的二叉树是否是完全二叉树。
【提示】根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应满足：①若某结点没有左孩子，则一定无右孩子；②若某结点缺（左或右）孩子，则其所有后继一定无孩子。因此，可采用按层次遍历二叉树的方法依次对每个结点进行判断。这里增加一个标志以表示所有已扫描过的结点均有左、右孩子，将局部判断结果存入CM中，CM表示整个二叉树是否是完全二叉树，B为1表示到目前为止所有结点均有左右孩子。 int CompleteBT(BiTree T) { Init_Queue(Q); /*初始化队列Q*/
B=1; CM=1;
if (T!=NULL) { In_Queue(Q,T);
while(!Empty_Queue(Q)) /*当队列不为空时执行循环*/ { p=Out_Queue(Q); if(p->lchild==NULL) { B=0; /*B=0表示缺少左、右孩子*/ if(rchild!=NULL) CM=0; /*CM=0表示不是完全二叉树*/
}
else {CM=B;
In_Queue(Q,p->lchild); /*左孩子入队列*/ if(p->rchild==NULL) B=0; else In_Queue(Q,p->rchild); /*右孩子入队列*/
}
}
return(CM);
} }
t->data=post[pr]; m=il;
while (in[m]!=post [pr] ) m++; if (m== il) if (m==ir)
t->lchild=NULL ; t->rchild=NULL;
else InPost ( in, post,il,m-1,pl,pl+m-1-il, t->lchild);
else InPost (in,post,m+1,ir,pr-ir+m,pr-1,t->rchild);