6.47.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

6.47④ 编写按层次顺序(同一层自左至右)遍历二叉树的算法。

要求实现下列函数：
void LevelOrder(BiTree bt, char *ss);
/* travel BiTree bt by level, Return result by ss. */

二叉链表类型定义：
typedef char TElemType;   // 设二叉树的元素为char类型
typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;

可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);

提示：可将遍历元素的值（字符）依次置入ss，并最后以'\0'结尾。
也可以用下列字符串函数产生ss：
int sprintf(char *buffer, char *format [, argument, ...]);
char *strcat(char *dest, char *src);
void LevelOrder(BiTree bt, char *ss)
/* travel BiTree bt by level, Return result by ss. */
{
  Queue Q;
  int i=0;
  struct BiTNode *p;
  InitQueue(Q);                         //建立工作队列
  EnQueue(Q,bt);
  if(!bt) ss[0]='\0';
  else{
     while(!QueueEmpty(Q))
       {
       DeQueue(Q,p);
       ss[i]=p->data;
       i++;
       if(p->lchild) EnQueue(Q,p->lchild);
       if(p->rchild) EnQueue(Q,p->rchild);
       }
     ss[i]='\0';
     }
}