第六章 树和二叉树.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

　}
　path[h]=NULL; //回溯
}//Find_h

6.54

Status CreateBitree_SqList(Bitree &T,SqList sa)//根据顺序存储结构建立二叉链表
{
　Bitree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针
　if(!sa.last)
　{
　　T=NULL; //空树
　　return;
　}
　ptr[1]=(BTNode*)malloc(sizeof(BTNode));
　ptr[1]->data=sa.elem[1]; //建立树根
　T=ptr[1];
　for(i=2;i<=sa.last;i++)
　{
　　if(!sa.elem[i]) return ERROR; //顺序错误
　　ptr[i]=(BTNode*)malloc(sizeof(BTNode));
　　ptr[i]->data=sa.elem[i];
　　j=i/2; //找到结点i的双亲j
　　if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子
　　else ptr[j]->lchild=ptr[i]; //i是j的左孩子
　}
　return OK;
}//CreateBitree_SqList

6.55

int DescNum(Bitree T)//求树结点T的子孙总数填入DescNum域中,并返回该数
{
　if(!T) return -1;
　else d=(DescNum(T->lchild)+DescNum(T->rchild)+2); //计算公式
　T->DescNum=d;
　return d;
}//DescNum
分析:该算法时间复杂度为O(n),n为树结点总数.注意:为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回-1而不是0.

6.56

BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针
{
　if(p->lchild) return p->lchild;
　else return p->rchild;
}//PreOrder_Next
分析:总觉得不会这么简单.是不是哪儿理解错了?

6.57

Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针
{
　if(p->rtag) return p->rchild; //p有后继线索
　else if(!p->parent) return NULL; //p是根结点
　else if(p==p->parent->rchild) return p->parent; //p是右孩子
　else if(p==p->parent->lchild&&p->parent->tag)
　　return p->parent; //p是左孩子且双亲没有右孩子
　else //p是左孩子且双亲有右孩子
　{
　　q=p->parent->rchild;
　　while(!q->ltag||!q->rtag)
　　{
　　　if(!q->ltag) q=q->lchild;
　　　else q=q->rchild;
　　} //从p的双亲的右孩子向下走到底
　return q;
　}//else
}//PostOrder_Next

6.58

Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)//在中序线索二叉树T的结点p下插入子树x
{
　if(!p->ltag&&!p->rtag) return INFEASIBLE; //无法插入
　if(p->ltag) //x作为p的左子树
　{
　　s=p->lchild; //s为p的前驱
　　p->ltag=Link;
　　p->lchild=x;
　　q=x;
　　while(q->lchild) q=q->lchild;
　　q->lchild=s; //找到子树中的最左结点,并修改其前驱指向s
　　q=x;
　　while(q->rchild) q=q->rchild;
　　q->rchild=p; //找到子树中的最右结点,并修改其前驱指向p
　}
　else //x作为p的右子树
　{
　　s=p->rchild; //s为p的后继
　　p->rtag=Link;
　　p->rchild=x;
　　q=x;
　　while(q->rchild) q=q->rchild;
　　q->rchild=s; //找到子树中的最右结点,并修改其前驱指向s
　　q=x;
　　while(q->lchild) q=q->lchild;
　　q->lchild=p; //找到子树中的最左结点,并修改其前驱指向p
　}
　return OK;
}//Insert_BiThrTree

6.59

void Print_CSTree(CSTree T)//输出孩子兄弟链表表示的树T的各边
{
　for(child=T->firstchild;child;child=child->nextsib)
　{
　　printf("(%c,%c),",T->data,child->data);
　　Print_CSTree(child);
　}
}//Print_CSTree

6.60

int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目
{
　if(!T->firstchild) return 1; //叶子结点
　else
　{
　　count=0;
　　for(child=T->firstchild;child;child=child->nextsib)
　　　count+=LeafCount_CSTree(child);
　　return count; //各子树的叶子数之和
　}
}//LeafCount_CSTree

6.61

int GetDegree_CSTree(CSTree T)//求孩子兄弟链表表示的树T的度
{
　if(!T->firstchild) return 0; //空树
　else
　{
　　degree=0;
　　for(p=T->firstchild;p;p=p->nextsib) degree++;//本结点的度
　　for(p=T->firstchild;p;p=p->nextsib)
　　{
　　　d=GetDegree_CSTree(p);
　　　if(d>degree) degree=d; //孩子结点的度的最大值
　　}
　　return degree;
　}//else
}//GetDegree_CSTree

6.62

int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度
{
　if(!T) return 0; //空树
　else
　{
　　for(maxd=0,p=T->firstchild;p;p=p->nextsib)
　　　if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度
　　return maxd+1;
　}
}//GetDepth_CSTree

6.63

int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度
{
　return SubDepth(A.r);
}//GetDepth_CTree

int SubDepth(int T)//求子树T的深度
{
　if(!A.nodes[T].firstchild) return 1;
　for(sd=1,p=A.nodes[T].firstchild;p;p=p->next)
　　if((d=SubDepth(p->child))>sd) sd=d;
　return sd+1;
}//SubDepth

6.64

int GetDepth_PTree(PTree T)//求双亲表表示的树T的深度
{
　maxdep=0;
　for(i=0;i<T.n;i++)
　{
　　dep=0;
　　for(j=i;j>=0;j=T.nodes[j].parent) dep++; //求每一个结点的深度
　　if(dep>maxdep) maxdep=dep;
　}
　return maxdep;
}//GetDepth_PTree

6.65

char Pred,Ind; //假设前序序列和中序序列已经分别储存在数组Pre和In中

Bitree Build_Sub(int Pre_Start,int Pre_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表
{
　sroot=(BTNode*)malloc(sizeof(BTNode)); //建根
　sroot->data=Pre[Pre_Start];
　for(i=In_Start;In[i]!=sroot->data;i++); //在中序序列中查找子树根
　leftlen=i-In_Start;
　rightlen=In_End-i; //计算左右子树的大小
　if(leftlen)
　{
　　lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1);
　　sroot->lchild=lroot;
　} //建左子树,注意参数表的计算
　if(rightlen)
　{
　　rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);
　　sroot->rchild=rroot;
　} //建右子树,注意参数表的计算
　return sroot; //返回子树根
}//Build_Sub

main()
{
　...
　Build_Sub(1,n,1,n); //初始调用参数,n为树结点总数
　...
}
分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.

6.66

typedef struct{
　　　　　　　　  　CSNode *ptr;
　　　　　　　　　 CSNode *lastchild;
　　　　　　　　 } NodeMsg; //结点的指针和其最后一个孩子的指针

Status Bulid_CSTree_PTree(PTree T)//由树T的双亲表构造其孩子兄弟链表
{
　NodeMsg Treed;
　for(i=0;i<T.n;i++)
　{
　　Tree[i].ptr=(CSNode*)malloc(sizeof(CSNode));
　　Tree[i].ptr->data=T.node[i].data; //建结点
　　if(T.nodes[i].parent>=0) //不是树根
　　{
　　　j=T.nodes[i].parent; //本算法要求双亲表必须是按层序存储
　　　if(!(Tree[j].lastchild)) //双亲当前还没有孩子
　　　　Tree[j].ptr->firstchild=Tree[i].ptr; //成为双亲的第一个孩子
　　　else //双亲已经有了孩子
　　　　Tree[j].lastchild->nextsib=Tree[i].ptr; //成为双亲最后一个孩子的下一个兄弟
　　　Tree[j].lastchild=Tree[i].ptr; //成为双亲的最后一个孩子
　　}//if
　}//for
}//Bulid_CSTree_PTree

6.67

typedef struct{
　　　　　　　　char data;
　　　　　　　　CSNode *ptr;
　　　　　　　　CSNode *lastchild;
　　　　　　　} NodeInfo; //结点数据,结点指针和最后一个孩子的指针

Status CreateCSTree_Duplet(CSTree &T)//输入二元组建立树的孩子兄弟链表
{
　NodeInfo Treed;
　n=1;k=0;
　if(getchar()!='^') return ERROR; //未按格式输入
　if((c=getchar())=='^') T=NULL; //空树
　Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode));
　Tree[0].data=c;
　Tree[0].ptr->data=c;
　while((p=getchar())!='^'&&(c=getchar())!='^')
　{
　　Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode));
　　Tree[n].data=c;
　　Tree[n].ptr->data=c;
　　for(k=0;Tree[k].data!=p;k++); //查找当前边的双亲结点
　　if(Tree[k].data!=p) return ERROR; //未找到:未按层序输入
　　r=Tree[k].ptr;
　　if(!r->firstchild)
　　　r->firstchild=Tree[n].ptr;
　　else Tree[k].lastchild->nextsib=Tree[n].ptr;
　　Tree[k].lastchild=Tree[n].ptr; //这一段含义同上一题
　　n++;
　}//while
　return OK;
}//CreateCSTree_Duplet

6.68

Status CreateCSTree_Degree(char node[ ],int degree[ ])//由结点的层序序列和各结点的度构造树的孩子兄弟链表
{
　CSNode * ptrd; //树结点指针的辅助存储
　ptr[0]=(CSNode*)malloc(sizeof(CSNode));
　i=0;k=1; //i为当前结点序号,k为当前孩子的序号
　while(node[i])
　{
　　ptr[i]->data=node[i];
　　d=degree[i];
　　if(d)
　　{
　　　ptr[k++]=(CSNode*)malloc(sizeof(CSNode)); //k为当前孩子的序号
　　　ptr[i]->firstchild=ptr[k]; //建立i与第一个孩子k之间的联系
　　　for(j=2;j<=d;j++)
　　　{
　　　　ptr[k++]=(CSNode*)malloc(sizeof(CSNode));
　　　　ptr[k-1]->nextsib=ptr[k]; //当结点的度大于1时,为其孩子建立兄弟链表
　　　}//for
　　}//if
　i++;
　}//while
}//CreateCSTree_Degree

6.69

void Print_BiTree(BiTree T,int i)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0
{
　if(T->rchild) Print_BiTree(T->rchild,i+1);
　for(j=1;j<=i;j++) printf(" "); //打印i个空格以表示出层次
　printf("%c\n",T->data); //打印T元素,换行
　if(T->lchild) Print_BiTree(T->rchild,i+1);
}//Print_BiTree
分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左.

6.70

Status CreateBiTree_GList(BiTree &T)//由广义表形式的输入建立二叉链表
{
　c=getchar();
　if(c=='#') T=NULL; //空子树
　else
　{
　　T=(CSNode*)malloc(sizeof(CSNode));
　　T->data=c;
　　if(getchar()!='(') return ERROR;
　　if(!CreateBiTree_GList(pl)) return ERROR;
　　T->lchild=pl;
　　if(getchar()!=',') return ERROR;
　　if(!CreateBiTree_GList(pr)) return ERROR;
　　T->rchild=pr;
　　if(getchar()!=')') return ERROR; //这些语句是为了保证输入符合A(B,C)的格式
　}
　return OK;
}//CreateBiTree_GList

6.71

void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0
{
　for(j=1;j<=i;j++) printf(" "); //留出i个空格以表现出层次
　printf("%c\n",T->data); //打印元素,换行
　for(p=T->firstchild;p;p=p->nextsib)
　　Print_CSTree(p,i+1); //打印子树
}//Print_CSTree

6.72

void Print_CTree(int e,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次
{
　for(j=1;j<=i;j++) printf(" "); //留出i个空格以表现出层次
　printf("%c\n",T.nodes[e].data); //打印元素,换行
　for(p=T.nodes[e].firstchild;p;p=p->next)
　　Print_CSTree(p->child,i+1); //打印子树
}//Print_CSTree

main()
{
　...
　Print_CTree(T.r,0); //初次调用时i=0
　...
}//main

6.73

char c; //全局变量,指示当前字符

Status CreateCSTree_GList(CSTree &T)//由广义表形式的输入建立孩子兄弟链表
{
　c=getchar();
　T=(CSNode*)malloc(sizeof(CSNode));
　T->data=c;
　if((c=getchar())=='(') //非叶结点
　{
　　if(!CreateCSTree_GList(fc)) return ERROR; //建第一个孩子
　　T->firstchild=fc;
　　for(p=fc;c==',';p->nextsib=nc,p=nc) //建兄弟链
　　　if(!CreateCSTree_GList(nc)) return ERROR;
　　p->nextsib=NULL;
　　if((c=getchar())!=')') return ERROR; //括号不配对
　}
　else T->firtchild=NULL; //叶子结点
　return OK;
}//CreateBiTree_GList
分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断.

6.74

void PrintGlist_CSTree(CSTree T)//按广义表形式输出孩子兄弟链表表示的树
{
　printf("%c",T->data);
　if(T->firstchild) //非叶结点
　{
　　printf("(");
　　for(p=T->firstchild;p;p=p->nextsib)
　　{
　　　PrintGlist_CSTree(p);
　　　if(p->nextsib) printf(","); //最后一个孩子后面不需要加逗号
　　}
　　printf(")");
　}//if
}//PrintGlist_CSTree

6.75

char c;
int pos=0; //pos是全局变量,指示已经分配到了哪个结点

Status CreateCTree_GList(CTree &T,int &i)//由广义表形式的输入建立孩子链表
{
　c=getchar();
　T.nodes[pos].data=c;
　i=pos++; //i是局部变量,指示当前正在处理的子树根
　if((c=getchar())=='(') //非叶结点
　{
　　CreateCTree_GList();
　　p=(CTBox*)malloc(sizeof(CTBox));
　　T.nodes[i].firstchild=p;
　　p->child=pos; //建立孩子链的头
　　for(;c==',';p=p->next) //建立孩子链
　　{
　　　CreateCTree_GList(T,j); //用j返回分配得到的子树根位置
　　　p->child=j;
　　　p->next=(CTBox*)malloc(sizeof(CTBox));
　　}
　　p->next=NULL;
　　if((c=getchar())!=')') return ERROR; //括号不配对
　}//if
　else T.nodes[i].firtchild=NULL; //叶子结点
　return OK;
}//CreateBiTree_GList
分析:该算法中,pos变量起着"分配"结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n.

6.76

void PrintGList_CTree(CTree T,int i)//按广义表形式输出孩子链表表示的树
{
　printf("%c",T.nodes[i].data);
　if(T.nodes[i].firstchild) //非叶结点
　{
　　printf("(");
　　for(p=T->firstchild;p;p=p->nextsib)
　　{
　　　PrintGlist_CSTree(T,p->child);
　　　if(p->nextsib) printf(","); //最后一个孩子后面不需要加逗号
　　}
　　printf(")");
　}//if
}//PrintGlist_CTree