在二叉树的遍历这篇博客中 https://www.cnblogs.com/wkfvawl/p/9901462.html
对于二叉树的层次遍历我只是给出了基于 C++ STL 的代码, 这里我使用数据结构的链表, 构建一个链队列来实现. 这也算是我第一次使用链队列来完成某个任务, 链队列代码还是来自课本, 因为之前使用 C++ STL 时, queue 中的某些函数是有返回值的列如 Q.front(), 而有些却没有返回值像 Q.push(p),Q.pop(), 就连有没有参数也是不同的, 在这里我没有改动课本上的代码来适应自己的习惯, 还是按照课本上来所有函数都是有返回值的, 对于想要返回值的函数直接使用地址传递.
- #include<stdio.h>
- #include<malloc.h>
- #define TRUE 1
- #define FALSE 0
- #define MAX 20
- typedef struct BTNode /* 节点结构声明 */
- {
- char data ; /* 节点数据 */
- struct BTNode *lchild;
- struct BTNode *rchild ; /* 指针 */
- }*BiTree;
- typedef struct Node/// 队列中结点结构
- {
- BiTree data;/// 数据域 (二叉树结构体)
- struct Node *next;/// 指针域
- } LinkQNode;
- typedef struct/// 队列结构
- {
- LinkQNode *front;/// 队头指针
- LinkQNode *rear;/// 队尾指针
- } LinkQueue;
- void InitLinkQueue(LinkQueue *Q)/// 初始化列队列
- {
- Q->front=(LinkQNode *)malloc(sizeof(LinkQNode));
- Q->rear=Q->front;/// 队头指针和队尾指针都指向头结点
- Q->front->next=NULL;
- }
- int IsLQEmpty(LinkQueue *Q)/// 判断队列是否为空
- {
- if(Q->front==Q->rear)
- {
- return TRUE;
- }
- else
- {
- return FALSE;
- }
- }
- int EnLinkQueue(LinkQueue *Q,BiTree x)
- {
- LinkQNode *NewNode;
- NewNode=(LinkQNode *)malloc(sizeof(LinkQNode));/// 开辟新结点
- if(NewNode!=NULL)
- {
- NewNode->data=x;
- NewNode->next=NULL;
- Q->rear->next=NewNode;/// 在队尾插入结点
- Q->rear=NewNode;/// 修改队尾指针
- return TRUE;
- }
- else/// 溢出
- {
- return FALSE;
- }
- }
- int DeLinkQueue(LinkQueue *Q,BiTree *x)/// 删除对头指针, 并用 x 返回删除的值
- {
- LinkQNode *p;
- if(Q->front==Q->rear)
- {
- return FALSE;
- }
- p=Q->front->next;///p 指向对头元素
- Q->front->next=p->next;/// 对头元素 p 出队
- if(Q->rear==p)/// 如果队列中只有一个元素 p, 则 p 出队后变成空队
- {
- Q->rear=Q->front;
- }
- *x=p->data;
- free(p);
- return TRUE;
- }
- int GetLQHead(LinkQueue *Q,BiTree *x)/// 获取队头元素, 用 x 返回其值
- {
- LinkQNode *p;/// 中间变量
- if(Q->front==Q->rear)
- {
- return FALSE;
- }
- p=Q->front->next;
- *x=p->data;
- free(p);
- return 1;
- }
- BiTree createBiTree(BiTree t) /* 先序遍历创建二叉树 */
- {
- char s;
- printf("\nplease input data:(exit for #)");
- s=getchar();
- if(s=='#')
- {
- t=NULL;
- return t;
- }
- t=(BiTree)malloc(sizeof(struct BTNode));
- if(t==NULL)
- {
- printf("Memory alloc failure!");
- exit(0);
- }
- t->data=s;
- t->lchild=createBiTree(t->lchild); /* 递归建立左子树 */
- t->rchild=createBiTree(t->rchild); /* 递归建立右子树 */
- return t;
- }
- void LevelOrder(BiTree p)
- {
- LinkQueue *Q;
- Q=(LinkQueue *)malloc(sizeof(LinkQueue));
- InitLinkQueue(Q);
- EnLinkQueue(Q,p);
- while(!IsLQEmpty(Q))
- {
- DeLinkQueue(Q,&p);/// 出队列并取队头元素
- printf("%c",p->data);// 左右孩子入队
- if(p->lchild!=NULL)
- {
- EnLinkQueue(Q,p->lchild);
- }
- if(p->rchild!=NULL)
- {
- EnLinkQueue(Q,p->rchild);
- }
- }
- printf("\n");
- }
- int main()
- {
- BiTree t=NULL;
- t=createBiTree(t);
- printf("\n\n 层次遍历序列:");
- LevelOrder(t);
- release(t);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2851168.html