队列实现二叉树遍历.docx

#includestdio.h#includestdlib.h#includemalloc.h#define OVERFLOW 2#define OK 1#define ERROR 0typedef struct BiTNode //定义二叉树{ char data; struct BiTNode *lchild; struct BiTNode *rchild;}BiTNode,*BiTree ;typedef struct QNode//队列节点结构体{BiTree data;struct QNode *next;}QNode,*QueuePtr;typedef struct //队列{QueuePtr front;QueuePtr rear; /* 队头、队尾指针 */}LinkQueue;char CreateBiTree(BiTreeT) //创建二叉树{ char ch; scanf(%c,ch); if(ch==#) T=NULL; else{ if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); }return OK;}void visit(BiTree T){if(T-data!=#)printf(%c,T-data);}void PreOrder(BiTree T)//先序遍历{ if(T) { visit(T);PreOrder(T-lchild); PreOrder(T-rchild); }}void InOrder(BiTree T)//中序遍历{ if(T) { InOrder(T-lchild); visit(T);InOrder(T-rchild); }}void PostOrder(BiTree T)//后序遍历{ if(T) { PostOrder(T-lchild);PostOrder(T-rchild); visit(T); }}void InitQueue(LinkQueue *Q){(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if((*Q).front)(*Q).front-next=NULL;}int QueueEmpty(LinkQueue Q){if(Q.front==Q.rear)return 0;return 1;}void EnQueue(LinkQueue *Q,BiTree e){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(p)p-data=e;p-next=NULL; (*Q).rear-next=p;(*Q).rear=p;}void DeQueue(LinkQueue *Q,BiTree *e){QueuePtr p;if((*Q).front!=(*Q).rear){p=(*Q).front-next;*e=p-data;(*Q).front-next=p-next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);}}void Level(BiTree T){/*层次遍历*/LinkQueue q;BiTree p;InitQueue(q);/*初始化一个空的队列*/EnQueue(q,T);/*入队*/while(QueueEmpty(q)){DeQueue(q,p);/*出队*/printf(%c ,p-data);if(p-lchild)EnQueue(q,p-lchild);if(p-rchild)EnQueue(q,p-rchild);}}void main(){ BiTree T; CreateBiTree(T); printf(先序遍历:\n); PreOrder(T); printf(\n中序遍历:\n); InOrder(T); printf(\n后序遍历:\n); PostOrder(T); printf(\n层次遍历:\n); Level(T); printf(\n);}