上海公司注册地址可以是住宅吗_新开网店怎么推广_曲靖seo_seo搜索推广

我们先来了解一下什么是二叉树的层序遍历！

层序遍历的理解

下图是一棵二叉树，

层序遍历这棵二叉树的顺序是：

1→2→3→4→5→6→7，

看图也很简单易懂，

第一层→第二层→第三层。

层序遍历的实现

如果二叉树的结点以数组的方式储存，那就是打印一遍数组就完成了层序遍历。

但是，我们用的是链式结构，难度就会蹭蹭往上涨……

我们实现层析遍历需要使用队列(queue).

队列的特点是先进先出，观察下图的橙色箭头→:

 

只要入队列的顺序是1234567，那么出队列的顺序也是1234567.

我们就实现了层序遍历。

 

先上队列的代码，

头文件Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{
//指向队列头的指针QNode* phead;
//指向队列尾的指针QNode* ptail;int size;
}Queue;//队列初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//在队尾插入元素
void QueuePush(Queue* pq, QDataType x);
//删除队头元素
void QueuePop(Queue* pq);
//队列长度
int QueueSize(Queue* pq);
//返回队头元素的值
QDataType QueueFront(Queue* pq);
//返回队尾元素的值
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

源文件Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* temp = cur->next;free(cur);cur = temp;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* temp = (QNode*)malloc(sizeof(QNode));if (temp == NULL) {perror("malloc fail");return;}temp->next = NULL;temp->val = x;if (pq->ptail == NULL) {pq->phead = pq->ptail = temp;}else{pq->ptail->next = temp;pq->ptail = temp;}pq->size++;}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size!=0);QNode* temp = pq->phead->next;free(pq->phead);pq->phead = temp;if (pq->phead == NULL) {pq->ptail = NULL;}pq->size--;
}
int QueueSize(Queue* pq) {assert(pq);return pq->size;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;
}

然后是层序遍历的实现。

void TreeLevelOrder(BTNode* root)
{Queue pq;QueueInit(&pq);//根结点先入队列if (root){QueuePush(&pq, root);}while (!QueueEmpty(&pq)){
//存着队列头的结点BTNode* front = QueueFront(&pq);
//删除队列头的节点QueuePop(&pq);
//打印队列头结点的值printf("%d ", front->data);
//左右节点先后入队列if(front->left)QueuePush(&pq, front->left);if(front->right)QueuePush(&pq, front->right);}QueueDestroy(&pq);}