一，层序遍历算法
二叉树的层序遍历是一层一层的从左到右遍历，现在问题是二叉树不支持随机访问，因此，我们需要借助其它结构来实现这一功能。通常，对于这种遍历算法我们要借助队结构的概念。
补充：树的层序遍历也叫做广度优先遍历，而广度优先遍历通常要借助队列的结构实现。
1-1，队列结构的设立
队列的结构相信大家都已非常熟悉了，如果队列结构不清楚的可以观看本人以前讲解队列的文章，本文在这里就不做过多说明了。我们可定义一个头文件，将队列的基础算法写进去，其中，要注意的是队列中的元素是树中的结点，因为往队列中装数据装的是树的结点，不可直接装树结点的数据，否则设置此结构几乎没用，下文分析时会详细说明，在这里我们只需先构造队列中的基础算法即可。如下：
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef struct Tree DataType; typedef struct Node { DataType* val; struct Node* next; }Node; typedef struct Queue { Node* head; Node* tail; }Queue; void QueueInit(Queue* Q) { Q->head = Q->tail = 0; } void QueuePush(Queue* Q, DataType* x) { Node* node = (Node*)malloc(sizeof(Node)); if (!node) { return; } node->val = x; node->next = 0; if (!Q->head) { Q->head = Q->tail = node; } else { Q->tail->next = node; Q->tail = node; } } void QueuePop(Queue* Q) { if (!Q->head) { return; } Node* node = Q->head->next; free(Q->head); Q->head = node; } bool QueueEmpty(Queue* Q) { return Q->head == NULL; } void QueueDestroy(Queue* Q) { if (!Q->head) { return; } Node* node = Q->head->next; while (Q->head != Q->tail) { free(Q->head); Q->head = node; node = node->next; } free(Q->head); free(Q); }
1-2，逻辑分析
队列结构设置完后，我们要考虑的是如何将每一层的数据从左到右放入队列中。如果直接将树结点中的数据直接导入，很显然，这跟用不用队列结构没多大关系，相当于直接层序遍历二叉树。因此，我们要考虑将树中结点导入，然后，利用结点间相连问题进行层序导入队列中。具体步骤和说明如下：
首先，要将根结点导入队列，然后输出队列中首结点的数据，并先将此结点的左孩子导入进队列，再将右孩子导入进队列，最后删除首结点，以此类推，不断进行循环，当队列为空时相当于已层序遍历完整个二叉树。至于原因是因为我们输出首结点的元素后删除了首结点，所以当进行下一次循环将首结点的左右孩子导入时，相当于从树的下一层开始，从左到右导入数据。
代码如下：
void LevelOrder(Tree* root) { //空树直接退出 if (!root) { return; } //建立队列结构 Queue* Q = (Queue*)malloc(sizeof(Queue)); QueueInit(Q); //先把根结点推入进去 QueuePush(Q, root); //进行遍历，先将数据输出，导入队列左右孩子后要出队，即删除，当队为空时已遍历完。 while (!QueueEmpty(Q)) { fprintf(stdout, "%d ", Q->head->val->val); if (Q->head->val->leftchild) { QueuePush(Q, Q->head->val->leftchild); } if (Q->head->val->rightchild) { QueuePush(Q, Q->head->val->rightchild); } QueuePop(Q); } }
算法演示：
//设定队列结构和必要的头文件 #include "Queue.h" typedef struct Tree { int val;//数据 struct Tree* leftchild;//左孩子结点 struct Tree* rightchild;//右孩子结点 }Tree; //创建二叉树数据为x的结点 Tree* CreatNode(int x) { Tree* node = (Tree*)malloc(sizeof(Tree)); node->val = x; node->leftchild = 0; node->rightchild = 0; return node; } //二叉树的销毁 void TreeDestroy(Tree* root) { if (!root) { return; } TreeDestroy(root->leftchild); TreeDestroy(root->rightchild); free(root); } //层序遍历算法(广度优先遍历) void LevelOrder(Tree* root) { //空树直接退出 if (!root) { return; } //建立队列结构 Queue* Q = (Queue*)malloc(sizeof(Queue)); QueueInit(Q); //先把根结点推入进去 QueuePush(Q, root); //进行遍历，先将数据输出，导入队列左右孩子后要出队，即删除，当队为空时已遍历完。 while (!QueueEmpty(Q)) { fprintf(stdout, "%d ", Q->head->val->val); if (Q->head->val->leftchild) { QueuePush(Q, Q->head->val->leftchild); } if (Q->head->val->rightchild) { QueuePush(Q, Q->head->val->rightchild); } QueuePop(Q); } } int main() { //手动构建二叉树 Tree* node1 = CreatNode(1); Tree* node2 = CreatNode(2); Tree* node3 = CreatNode(3); Tree* node4 = CreatNode(4); Tree* node5 = CreatNode(5); Tree* node6 = CreatNode(6); Tree* node7 = CreatNode(7); Tree* node8 = CreatNode(8); Tree* node9 = CreatNode(9); Tree* node10 = CreatNode(10); Tree* node11 = CreatNode(11); Tree* node12 = CreatNode(12); Tree* node13 = CreatNode(13); Tree* node14 = CreatNode(14); Tree* node15 = CreatNode(15); //结点的连接 node1->leftchild = node2; node1->rightchild = node4; node2->leftchild = node3; node4->leftchild = node5; node4->rightchild = node6; node2->rightchild = node7; node3->leftchild = node8; node3->rightchild = node9; node7->leftchild = node10; node7->rightchild = node11; node5->leftchild = node12; node5->rightchild = node13; node6->leftchild = node14; node6->rightchild = node15; LevelOrder(node1); TreeDestroy(node1); return 0; }
接下来我们用经典题型来进行解说二叉树的运用。
【数据结构与算法】二叉树的综合运用--2https://developer.aliyun.com/article/1424486?spm=a2c6h.13148508.setting.26.214f4f0e2QJGOK
