1.txt

清华大学出版社严蔚敏编著数据结构习题答案

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. */
{BiTree p;Queue Q ;
 InitQueue(Q);
 if(bt){    
    EnQueue(Q,bt);
    while(!QueueEmpty(Q)){
        DeQueue(Q,p);
        *ss=p->data;
        ss++;
        if(p->lchild){EnQueue(Q,p->lchild);}
        if(p->rchild){EnQueue(Q,p->rchild);}
    }
 }
 *ss='\0';
}