二叉树层序遍历
目录：
层次遍历：
使用双向循环链表，尾部入队，头部出队。同时使用头结点方便出队和入队操作
函数声明：
void CreatTree(TreeNode **tree,char *data,int *index); //创建二叉树QueueNode *InitQueue(); //初始化队列void enQueue(TreeNode *tree,QueueNode * queue); //入队boolean isEmpty(QueueNode *queue); //判断队列是否为空QueueNode *deQueue(QueueNode *queue); //出队void levelTraverse(QueueNode *queue,TreeNode *tree); //层序遍历定义结构体：
#include #include //树typedef struct TreeNode{ char val; //保存树的内容 struct TreeNode *lchild; //指向树的左孩子 struct TreeNode *rchild; //指向树的右孩子}TreeNode;//队列typedef struct QueueNode{ TreeNode *data;//存储二叉树结点 struct QueueNode *next; //指向下一结点 struct QueueNode *pre;//指向前一结点}QueueNode;层序遍历：
void levelTraverse(QueueNode *queue,TreeNode *tree){ //根结点入队 enQueue(tree,queue); while(!isEmpty(queue)) { //队列非空时出队 QueueNode *node = deQueue(queue); //访问结点 printf("%c\t",node->data->val); //判断二叉树是个否有左孩子 if(node->data->lchild) { //左孩子入队 enQueue(node->data->lchild,queue); } //判断二叉树是否有右孩子 if(node->data->rchild) { //右孩子入队 enQueue(node->data->rchild,queue); } } printf("\n");}初始化队列：
//初始化队列QueueNode *InitQueue(){ QueueNode * queue = (QueueNode *)malloc(sizeof(QueueNode)); queue->data = NULL; //初始化队列数据指向为空 queue->pre = queue; //初始化队列头结点指向 queue->next = queue; //初始化队列头结点指向 return queue;}入队操作：
//入队操作void enQueue(TreeNode *tree,QueueNode *queue){ QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode)); if(node == NULL) return ; node->data = tree; //存储传入元素的地址 node->pre = queue->pre; //新结点的pre指向队列尾结点（双向循环链表 queue->pre 为尾结点） node->next = queue; //新结点的next指向队头 queue->pre->next = node; //队列尾结点指向新结点 queue->pre = node; //队头的pre指向新结点（此时新结点更新为尾结点）}出队操作：
//出队操作（头部出队）QueueNode *deQueue(QueueNode *queue){ if(isEmpty(queue)) { return NULL; } else { QueueNode *node = queue->next; //辅助结点，指向首元素 node->next->pre = queue; //出队结点的下一结点pre指针指向头结点 queue->next = node->next; //头结点的next指针指向删除结点的next指向的结点 return node;}}判断队列是否为空：
boolean isEmpty(QueueNode *queue){ if(queue->next == queue) return TRUE; return FALSE;}程序：
#include "inorder.h"void main(){ TreeNode *tree; QueueNode *queue = InitQueue(); //初始化队列 int index = 0; char *data = "ABD##E##CF##G##"; CreatTree(&tree,data,&index);//创建二叉树 levelTraverse(queue,tree); //层序遍历 system("pause"); return ;}void CreatTree(TreeNode **T,char *data,int *index){ char ch; ch = data[*index]; *index += 1; if(ch == '#') { //此时为空结点 *T = NULL; } else { //非空结点 *T = (TreeNode *)malloc(sizeof(TreeNode)); (*T)->val = ch; //创建左子树 CreatTree(&((*T)->lchild),data,index); //创建右子树 CreatTree(&((*T)->rchild),data,index); }}//初始化队列QueueNode *InitQueue(){ QueueNode * queue = (QueueNode *)malloc(sizeof(QueueNode)); queue->data = NULL; //初始化队列数据指向为空 queue->pre = queue; //初始化队列头结点指向 queue->next = queue; //初始化队列头结点指向 return queue;}//入队操作void enQueue(TreeNode *tree,QueueNode *queue){ QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode)); if(node == NULL) return ; node->data = tree; //存储传入元素的地址 node->pre = queue->pre; //新结点的pre指向队列尾结点（双向循环链表 queue->pre 为尾结点） node->next = queue; //新结点的next指向队头 queue->pre->next = node; //队列尾结点指向新结点 queue->pre = node; //队头的pre指向新结点（此时新结点更新为尾结点）}//出队操作（头部出队）QueueNode *deQueue(QueueNode *queue){ if(isEmpty(queue)) { return NULL; } else { QueueNode *node = queue->next; //辅助结点，指向首元素 node->next->pre = queue; //出队结点的下一结点pre指针指向头结点 queue->next = node->next; //头结点的next指针指向删除结点的next指向的结点 return node;}}boolean isEmpty(QueueNode *queue){ if(queue->next == queue) return TRUE; return FALSE;}void levelTraverse(QueueNode *queue,TreeNode *tree){ //根结点入队 enQueue(tree,queue); while(!isEmpty(queue)) { //队列非空时出队 QueueNode *node = deQueue(queue); printf("%c\t",node->data->val); //判断二叉树是个否有左孩子 if(node->data->lchild) { //左孩子入队 enQueue(node->data->lchild,queue); } //判断二叉树是否有右孩子 if(node->data->rchild) { //右孩子入队 enQueue(node->data->rchild,queue); } } printf("\n");}创建的二叉树图示：
测试结果：
图解分析：
程序使用双向循环链表，图解时为快速画图简单图示
声明：此文章为学习笔记，如有侵权请联系删除。