<转>二叉树的层次遍历

1. 首先将root节点enqueue。 2.循环, 直到queue为空： 从queue中dequeue一个节点并访问。如果此节点存在left child,　将其enqueue。如果存在right child, 将其enqueue。 /*按层次遍历二叉树，借助队列来实现，为简便编程，借助数组实现队列功能*/ #include "stdio.h" #include "conio.h" #include "stdlib.h" typedef char TElemType; typedef struct BiTNode {      TElemType data;      struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; /*先序创建二叉树*/ void createBiTree(BiTree *T) {      char c;      scanf("%c",&c);      if(c!='#')     {          *T=(BiTree)malloc(sizeof(BiTNode));          (*T)->data=c;          createBiTree(&((*T)->lchild));          createBiTree(&((*T)->rchild));      }     else          *T=NULL; } /*先序遍历二叉树*/ void preOrder(BiTree T) { if(T) {     printf("%c",T->data);     preOrder(T->lchild);     preOrder(T->rchild); } } /*按层遍历*/ void levelTraverse(BiTree T) {     BiTree Queue[20];                  BiTree p;     int front=0,rear=0;         　 /*表示队头指针和队尾指针*/     if(T)    {         p=T;                      　　　/*根指针入队*/        Queue[rear]=p;         rear=(rear+1)%20;         /*队尾指针加一对20取余，可实现循环队列，合理利用空间*/         while(front!=rear)        　 /*队不空*/         {              p=Queue[front];           /*出队，将值赋给p*/              printf("%c",p->data);              front=(front+1)%20;              if(p->lchild)           　　 /*如果p有左子树，将左子树入队*/             {                   Queue[rear]=p->lchild;                    rear=(rear+1)%20;              }              if(p->rchild)                  /*如果p有右子树，将右子树入队*/      {              Queue[rear]=p->rchild;              rear=(rear+1)%20;         }     } } } main() {      BiTree T;      createBiTree(&T);      preOrder(T);      printf("\n");      levelTraverse(T);      getch(); }