数据结构严蔚敏习题册 答案

if(T->lchild->data是操作符&&T->lchild->data优先级低于T->data) {

printf(\

if(!Print_Expression(T->lchild)) return ERROR; printf(\

} //注意在什么情况下要加括号

else if(!Print_Expression(T->lchild)) return ERROR;

if(T->rchild->data是操作符&&T->rchild->data优先级低于T->data) {

printf(\

if(!Print_Expression(T->rchild)) return ERROR; printf(\ }

else if(!Print_Expression(T->rchild)) return ERROR; }

else return ERROR; //非法字符 return OK;

}//Print_Expression 6.52

typedef struct{

BTNode node; int layer;

} BTNRecord; //包含结点所在层次的记录类型 int FanMao(Bitree T)//求一棵二叉树的\繁茂度\{

int countd; //count数组存放每一层的结点数 InitQueue(Q); //Q的元素为BTNRecord类型 EnQueue(Q,{T,0}); while(!QueueEmpty(Q)) {

DeQueue(Q,r); count[r.layer]++;

if(r.node->lchild) EnQueue(Q,{r.node->lchild,r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild,r.layer+1}); } //利用层序遍历来统计各层的结点数

h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++)

if(count[i]>maxn) maxn=count[i]; //求层最大结点数 return h*maxn; }//FanMao

分析:如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上会复杂一些,你能写出来吗? 6.53

int maxh;

Status Printpath_MaxdepthS1(Bitree T)//求深度等于树高度减一的最靠左的结点 {

Bitree pathd;

maxh=Get_Depth(T); //Get_Depth函数见6.44 if(maxh<2) return ERROR; //无符合条件结点 Find_h(T,1); return OK;

}//Printpath_MaxdepthS1

void Find_h(Bitree T,int h)//寻找深度为maxh-1的结点 {

path[h]=T;

if(h==maxh-1) {

for(i=1;path[i];i++) printf(\ exit; //打印输出路径 } else {

if(T->lchild) Find_h(T->lchild,h+1); if(T->rchild) Find_h(T->rchild,h+1); }

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的后序后继,并返回指