第6章习题答案.doc

第6章 树与二叉树
习题6
1.树与二叉树之间有什么区别与联系？
解：树与二叉树逻辑上都是树形结构，区别有三点：
（1）二叉树的度至多为2，树无此限制。
（2）二叉树有左右子树之分，树无此限制。
（3）二叉树允许为空，树一般不允许为空。
二叉树不是树的特例。
2.高度为的完全二叉树至少有多少个结点？至多有多少个结点？
解：至少有个结点，至多有个结点。和结点数之间的关系是ëû+1。
3.已知A[1..n]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？
解：根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号为ëi/2û，故A[i]和A[j]的最近的共同祖先可如下求出：
while(i/2!j/2)
if(i>j)i=i/2;
else j=j/2;
退出while后，若i/2=0，则最近共同祖先为根结点，否则共同祖先为i/2。
4.已知A[1..n]是一棵顺序存储的完全二叉树，求序号最小的叶子结点的下标。
解：根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是ën/2û，这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是ën/2û+1。
5.一棵深度为L的满k叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点进行编号求：
(1)各层的结点数是多少？
(2)编号为n的结点的双亲结点(若存在)的编号是多少？
(3)编号为n的结点的第i个孩子结点(若存在)的编号是多少？
(4)编号为n的结点有左右兄弟结点的条件是什么？如果有，其右兄弟结点的编号是多少？
解：(1)kh-1(h为层数)。
(2)因为该树上每层上均有kh-1个结点，从根开始编号为1，则结点i的从右向左数第2个孩子的结点编号为ki。设n为结点i的子女，则关系式(i-1)*k+2ni*k+1成立，因i是整数，故结点n的双亲i的编号为ën/kû+1。
(3)结点(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点n的第i个孩子的编号是(n-1)*k+1+i。
(4)根据以上分析，结点n有右兄弟的条件是，它不仅双亲的从右边的第一个子女，即(n-1)%k!=0，其右兄弟编号是n+1。
6.试证明，在具有n(n≥1)个结点的m叉树中，有n(m-1)+1个指针域是空的。
解：具有n个结点的m叉树共用n*m个指针。除根结点外，其余n-1个结点均有指针所指，故空指针数为n*m-(n-1)=n*(m-1)+1。
7.试找出满足下列条件的二叉树：
(1)先序序列与后序序列相同；
(2)中序序列与后序序列相同；
(3)先序序列与中序序列相同；
(4)中序序列与层次遍历序列相同。
解：(1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
(3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
(4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
8.设有一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF。请画出这棵二叉树。
解：按层次遍历，第一个结点（树不空）为根，该结点在中序序列中把序列分成左右两部分——左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若左子树为空，则层次序列中第二个结点为右子树的根。对右子树分析类似。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。

9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。
解：HIDJKEBLFGCA。
10.已知一棵二叉树的中序遍历序列为DGBAECHIF，后序遍历序列为：GDBEIHFCA。
(1)试画出该二叉树；
(2)试画出该二叉树的中序线索树；
(3)试画出该二叉树对应的森林。
解：（1）

（2）略
（3）

11.设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短。
解：字符A、B、C、D出现的次数为9、1、5、3。其哈夫曼编码如下：
A：1，B：000，C：01，D：001。
其哈夫曼树为：

12.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树T中，写出计算该算术表达式值的算法。
解：typedef struct Node{
ElemType data;
float val;
char optr;//只取+、-、*、/
struct Node *lchild,*rchild
}BiNode,*BiTree;
float PostEval(BiTree t){//以后序遍历算法求以二叉树表示的算术表达式的值
float lv,rv;
if(t!=NULL){
lv=PostEval(t->lchild);//
rv=PostEval(t->rchild);//
switch(t->optr){
case '+': value=lv+rv;break;
case '-':value=lv-rv;break;
case '*':value=lv*rv;break;

case '/':value=lv/rv;break;
}
}
return value;
}
13.假设二叉链表为二叉树的存储结构，编写判断给定的二叉树是否相似的算法。所谓二叉树t1和t2相似指的是：t1和t2都是空树；或者t1和t2的根结点是相似的，以及t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。
解：
int Like(BiTree t1, BiTree t2){
int like1,like2;
if(t1==NULL&&t2==NULL)return 1;
else if(t1==NULL|t2==NULL)return 0;
else{
like1=Like(t1->lchild,t2->lchild);
like2=Like(t1->rchild,t2->rchild);
return (like1 & like2);
}
}
14.假设二叉链表为二叉树的存储结构，编写递归算法，将二叉树中所有结点的左、右子树相互交换。
解：
void Exchange(BiTree &t){
if(t){
BiTree s;
s=t->lchild;t->lchild=t->rchild;t->rchild=s;
Exchange(t->lchild);
Exchange(t->rchild);
}
}
15.编写求双亲表示法表示的树的深度的算法。
解：
int Depth(PTree t){
int maxdepth=0,i,temp,f;
for(i=0;i-1){temp++;f=t.nodes[f].parent;}
if(temp>maxdepth)maxdepth=temp;
}
return maxdepth;
}
16.假设二叉链表为二叉树的存储结构，编写按层次遍历方式计算二叉树结点个数的算法。
解：
int Level(BiTree t){
int num=0;
LinkQueue Q;
BiTree p;
if(t){
InitQueue(Q);EnQueue(Q,t);
while(!QueueEmpty(Q)){
DeQueue(Q,p);num++;
if(p->lchild)EnQueue(Q,p->lchild);
if(p->rchild)EnQueue(Q,p->rchild);
}//while
}//if
return num;
}
17.编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双向链表，算法返回头结点的指针。
解：BiTree head,pre;//全局变量链表头指针head，pre
void CreateLeafList(BiTree t){
if(t){
CreateLeafList(t->lchild);//中序遍历左子树
if(t->lchild==NULL&&t->rchild==NULL)//叶子结点
if(head==NULL){//第一个叶子结点
head=new BiTNode; //生成头结点
head->lchild=NULL; head->rchild=t;//头结点的左链为空，右链指向第一个叶子结点
t->lchild=head;pre=t;//第一个叶子结点左链指向头结点，pre指向当前叶子结点
}
else{pre->rchild=t;t->lchild=pre;pre=t;};
CreateLeafList(t->rchild);
pre->rchild=NULL;
}
}
18.假设二叉链表为二叉树的存储结构，编写算法，按照括号表示法输出二叉树的所有结点。
解：其过程是：对于非空二叉树t，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“（”符号，然后递归处理左子树，输出一个“，”符号，递归处理右子树，最后输出一个“）”符号。
void DispBiTree(BiTree t){
if(t){
printf("%c",t->data);
if(t->lchild!=NULL||t->rchild!=NULL){
printf("(");
DispBiTree(t->lchild);
if(t->rchild!=NULL) printf(",");
DispBiTree(t->rchild);
printf(")");
}
}
}
19.假设二叉链表为二叉树的存储结构，编写算法，输出二叉树的所有叶子结点。
解：
void DispLeaf(BiTree t){
if(t){
if(t->lchild==NULL&&t->rchild==NULL)printf("%c ",t->data);
DispLeaf(t->lchild);
DispLeaf(t->rchild);
}
}
20.假设二叉链表为二叉树的存储结构，编写算法，输出值为x的结点的所有祖先。
解：
int Ancestor(BiTree t,ElemType x){
if(t==NULL)return 0;
if(t->data==x)return 1;
if(Ancestor(t->lchild,x)||Ancestor(t->rchild,x)){
printf("%c ",t->data);
return 1;
}
}
21.假设二叉链表为二叉树的存储结构，编写算法，输出所有叶子结点到根结点的路径。
解：利用后序非递归遍历的特点，将其中访问结点改为判断结点是否为叶子结点，若是，输出栈中所有结点值
void AllPathAncestor(BiTree t){
BiTNode *St[100];
BiTNode p;
int flag,i,top=-1;//栈指针初始化
if(t){
do{
while(t){ //t的所有左结点进栈
top++;
St[top]=t;
t=t->lchild;
}
p=NULL; //p指向栈顶结点的前一个已访问的结点
flag=1; //设置t的访问标记为已访问过
while(top!=-1&&flag){
t=St[top]; //出栈
if(t->rchild==p){
if(t->lchild==NULL&&t->rchild==NULL){ //若为叶子结点
for(i=top;i>0;i--) printf("%c->",St[i]->data); //输出栈中所有结点
printf("%c\n",St[0]->data);
}
top--;
p=t;//p指向刚访问过的结点
}
else{
t=t->rchild; //t指向右孩子结点
flag=0; //设置未访问标记
}
}
}while(top!=-1);
printf("\n");
}
}
22.编写算法，将二叉树的顺序存储结构转化为二叉链表存储结构。
解：typedef char ElemType;
typedef struct {//结点结构
ElemType *data;//数据元素
int n;//左右孩子指针
}SqBTree;
BiTree Trans(SqBTree a,int i){//数据元素放在数组a的从下标为1开始的单元中
BiTree t;
if(i>a.n)return NULL;//当i大于a的结点个数
if(a.data[i]=='#')return NULL;//当i对于的结点为空
t=new BiTNode;

t->data=a.data[i];
t->lchild=Trans(a,2*i);
t->rchild=Trans(a,2*i+1);
return t;
}
23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。
解：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若p左右子女均无，设其中序左线索指向其祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其右子女是p在后序下的前驱，若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，p在中序和后序下均无前驱。
BiThrTree InPostPre(BiThrTree t,BiThrTree p){
BiThrNode *q;
if(p->RTag==0)q=p->rchild;//若p有右子女，则右子女是其后序前驱
else if(p->LTag==0)q=p->lchild; //若p无右子女而有左子女，则左子女是其后序前驱
else if(p->lchild==NULL)q=NULL;//p是中序序列第一个结点，无后序前驱
else {//顺左线索向上找p的祖先，若存在，再找祖先的左子女
while(p->LTag==1&&p->lchild!=NULL)p=p->lchild;
if(p->LTag==0)q=p->lchild; //p结点的祖先的左子女是其后序前驱
else q=NULL; //仅右单支树（p是叶子），已上到根结点，p结点无后序前驱
}
return q;
}
24.写出按后序序列遍历中序线索二叉树的算法。
解：
BiThrTree LeftMost(BiThrTree t){//求结点t的最左子孙的左线索
BiThrTree p=t;
while(p->LTag==0)p=p->lchild;
if(p->lchild!=NULL&&p->lchild!=t)return(p->lchild);
else return NULL;
}
BiThrTree RightMost(BiThrTree t){//求结点t的最右子孙的右线索
BiThrTree p=t;
while(p->RTag==0)p=p->rchild;
if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild);
else return NULL;
}
int ISRightChild(BiThrTree t,BiThrTree &father){//若t是father的右孩子，返回1，否则返回0
father=LeftMost(t);
if(father&&father->rchild==t)return 1;
else return 0;
}
void PostOrderInThr(BiThrTree t){//后序遍历中序线索二叉树t
BiThrTree father,p=t->lchild;
int flag;
while(p!=t){
while(p->LTag==0)p=p->lchild;//沿左分子向下
if(p->RTag==0)flag=0;//左孩子为线索，右孩子为链，相当从左返回，p为叶子，相当从右返回
else flag=1;
while(flag==1){
printf("%c",p->data); //访问结点
if(ISRightChild(p,father)){p=father;flag=1;} //修改p指向双亲
else{//p是左孩子，用最右子孙的右线索找双亲
p=RightMost(p);
if(p&&p->RTag==1)flag=1;else flag=0;
}
}//while(flag==1)
if(flag==0&&p!=t)p=p->rchild;//转向当前结点的右分支
}
}
25.已知中序线索二叉树T的右子树不空。设计算法，将s所指结点作为T的右子树的一个叶子结点插入进去，并使之成为T的右子树的(中序序列)第一个结点。
解：若使新插入的结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左边的结点（设为p）处插入，使S成为结点p的左孩子。则S的前驱是T，后继是p。
void ThrTreeInsert(BiThrTree T, BiThrTree S){
BiThrTree p=T->rchild;//用p指向T的右子树中最左边的结点
while(p->LTag==0)p=p->lchild;
S->LTag=1;S->RTag=1;//S是叶子结点，其左右标记均为1
S->lchild=p->lchild; S->rchild=p;//S的前驱是根结点T，后继是结点p
p->lchild=S; p->LTag=0;//将p的左指针指向S，并修改左标记为0
}
26.写出在中序线索二叉树中找指定结点在中序下的前驱结点的算法。
解：BiThrTree InorderPre(BiThrTree p){
BiThrTree q;
if(p->LTag==1)//结点的左子树为空，结点左指针域为左线索，指向其前驱
return(p->lchild);
else{
q=p->lchild;//p结点左子树最右边结点时p结点的中序前驱
while(q->RTag)q=q->rchild;
return q;
}//if
}
11