数据结构与算法：SHIYAN2.TXT

/*题目：给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。*/
/*思路：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。*/
#define NULL 0
#define maxnum 20
typedef struct BiTNode
{ char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree()
{ char ch;
BiTree T;
scanf("%c",&ch);
if (ch==' ')
T=NULL;
else
{ if (!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(0);
T->data = ch;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return T;
}
levelorder (BiTree t) /*按层次遍历二叉树t*/
{ BiTree que[maxnum];
int rear,front;
if (t!=NULL)
{ front=0; /*置空队列*/
rear=1;
que[1]=t;
do
{ front=front%maxnum+1; /*出队*/
t=que[front];
printf("%c ",t->data);
if (t->lchild!=NULL) /*左子树的根结点入队*/
{ rear=rear%maxnum+1;
que[rear]=t->lchild;}
if (t->rchild!=NULL) /*右子树的根结点入队*/
{ rear=rear%maxnum+1;
que[rear]=t->rchild;}
}while (rear!=front); /*队列为空时结束*/
}
}
main()
{ BiTree root;
root=CreateBiTree();
levelorder (root);
}