将头结点 左右子树依次进入队列
最后从队头依次出队
#include<stdio.h>
#include<stdlib.h>
typedef struct BitNode{
char data;
struct BitNode *lchild,*rchild;
} *BiTree;
int CreateBiTree(BiTree &T){
char ch;
//char ch1;
ch =getchar();
//ch =ch1;
if(ch == '#' )
T =NULL;
else
{
if(!(T = (BitNode*)malloc(sizeof(BitNode)))) exit(0);
T->data = ch;//生成根结点；
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return 1;
}
int PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
else
return 0;
}
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);//后序遍历 最左边当结点左右子树到为空时候打印
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void LevelOrder(BiTree bt){
BiTree Q[10],p;
int front,rear;
if(bt == NULL) return ;
front = 0;
rear = 0;
Q[++rear]=bt;
while(front!=rear){
front++; p=Q[front];//p为头结点。。根据结点进如队列顺序 遍历
printf("%3c",p->data);
if(p->lchild!=NULL)
{rear++;Q[rear]=p->lchild;}//第一次循环左结点 右结点入队
if(p->rchild!=NULL)
{rear++;Q[rear]=p->rchild;}
}
}
int main(){
BiTree T;
CreateBiTree(T);
/* printf("prenordertraverse ");
PreOrderTraverse(T);
printf("
postordertraverse ");
PostOrderTraverse(T);
printf("
inordertraverse ");
InOrderTraverse(T);*/
LevelOrder(T);//测试数据abc###d##
return 0;
}