数据�l�构�W�六章算法设计题[17]_跨考网

1�Q�设某二叉树(w��i)�l�点�l�构�?/span>:

　　TYPE bitreptr=^bnodetp;

　　bnodetp=RECORD data:integer; lchild,rchild:bitreptr END;

　　试编写算法，计算每层中结�?/span>data域数值大�?/span>50的结点个敎ͼ��q�输�����些结点的data域的数值和序号。�?a target="_blank">北京工业大学 1998 �?/span>(10�?/span>)�?/span>

　　【参考答案�?/span>

　　[题目分析] 计算每层中结点值大�?/span>50的结点个敎ͼ�应按层次遍历。设一队列Q�Q�用front�?/span>rear分别指向队头和队���օ�素，last指向各层最右结点的位置。存攑ր�大�?/span>50的结点结构�ؓ(f��)

　　typedef struct {int level,value,idx; }node;//元素所在层受���值和本层中的序号

　　node a[],s;

　　void ValueGT50(BiTree bt)//查各层中�l�点值大�?/span>50的结点个敎ͼ�输出其值及(qi��ng)序号

　　{if(bt!=null)

　　{int front=0,last=1,rear=1,level=1,i=0,num=0;//num�?/span>>50的结点个�?/span>

　　BiTree Q[];Q[1]=bt;//根结点入�?/span>

　　while(front<=last)

　　{bt=Q[++front];

　　if(bt->data>50){s.level=level; s.idx=++i; s.value=bt->data; a[++num]=s;}

　　if(bt->lchild!=null) Q[++rear]=bt->lchild;//左子奛_��队列

　　if(bt->rchild!=null) Q[++rear]=bt->rchild;//叛_��奛_��队列

　　if(front==last) {last=rear; level++; i=0;} //本层最后一个结点已处理�?/span>

　　} //初始化下层：(x��)last指向下层最右结点，层号�?/span>1�Q�下�?/span>>50的序号初始�ؓ(f��)0

　　}//while

　　for(i=1;i<=num;i++) //输出data域数值大�?/span>50的结点的层号�?/span>data域的数值和序号

　　printf(“层�?/span>=%3d,本层序号=%3d�Q��?/span>=%3d”，a[i].level,a[i].idx,a[i].value);

　　}//���法ValueGT50�l�束