C语言实现二叉树层次遍历

什么是层次遍历？

对于一颗二叉树来说，从根节点开始，按从上到下、从左到右的顺序访问每一个结点。

注：每一个结点有且访问一次。

那我们如何来实现这个算法呢？

实现原理：

对于二叉树来说，它是一个递归的定义，我们要实现层次遍历必然要满足从上到下、从左到右这个要求，从根结点出发，我们可以将所有意义上的根结点都存储在队列之中，那我们可以使用队列先进先出的特点来实现要求的遍历。

这里我们需要引用队列来实现。

主体代码：

BiTree InitTree()//二叉树的创建{BiTree T =(BiTree) malloc(sizeof(Tree));char data;scanf("%c", &data);getchar();if (data == '#')//如果data为#则该子树为空值return NULL;else {T->data = data;printf("请输入%c的左子树:\n", data);T->lchild = InitTree();printf("请输入%c的右子树:\n", data);T->rchild = InitTree();}return T;}void ShowCengci(BiTree T){LinkQueue qu;InitQueue(&qu);//初始化队列enQueue(&qu, T);//根结点入队while (QueueEmpty(qu))//判断队列中是否为空{BiTree S = deQueue(&qu);//根节点出队printf("%c ", S->data);if (S->lchild != NULL)//判断左右子树是否为空，不为空则入队{enQueue(&qu, S->lchild);}if (S->rchild != NULL){enQueue(&qu, S->rchild);}}

队列的链式实现：

typedef struct BTree{char data;struct BTree* lchild;struct BTree* rchild;}Tree,*BiTree;typedef struct Queue{BiTree data;struct Queue* next;}Qnode,*Queueptr;typedef struct point{Queueptr front;//头指针Queueptr rear;//尾指针}LinkQueue;void InitQueue(LinkQueue* qu){qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode));if (qu->front == NULL)return;}void enQueue(LinkQueue* qu, BiTree S){Queueptr p = (Queueptr)malloc(sizeof(Qnode));if (p == NULL) {return;}if (S == NULL)return;p->data = S;p->next = NULL;qu->rear->next = p;qu->rear = p;}int QueueEmpty(LinkQueue qu){if (qu.front != qu.rear)return 1;elsereturn 0;}BiTree deQueue(LinkQueue* qu){if (qu->front == qu->rear)return;Queueptr p = qu->front->next;BiTree q = p->data;qu->front->next = p->next;if (qu->rear == p)qu->rear = qu->front;free(p);return q;}

通关上述代码可以实现对二叉树的层次遍历。