1. 背景
在上一篇中，我们利用递归很轻易的就实现了二叉树的前序、中序、后续遍历，但是层序遍历仅仅利用递归貌似是解决不了的。
在如上图的树中，我们如何先从上至下，然后从左至右的按层次进行遍历，即A-B-C-D-E-F-G这样的顺序呢。
2. 思路
每次在访问下一层次节点之前，应该将上一级节点输出，而上一级节点无疑从层次上先于下一级，我们联想到先进先出的队列模型，我们可以利用一个队列，在递归访问二叉树下一层次之前，将本层次的节点放入队列，这样就实现了输出时，也是按层次先后输出的。
之前有一版本写错了，层序遍历应该递归访问队列，每次输出一个层级，而不是递归二叉树。
感谢才情a指出问题，他的博客附上表示敬意
2020.2.25修正一版
3. 代码实现
#include<stdio.h> #define QUEUE_LENGTH 100 //队列最大元素个数 /* * 二叉树的层序遍历演示DEMO * 作者：熊猫大大 * 时间：2019-12-15 */ //二叉树结构体 typedef struct { char data;//数据区域(为了保存ABCD，直接用char当做数据域，便于和文章中的插图对应，稳！) struct BinaryTreeNode* left;//左子节点 struct BinaryTreeNode* right;//右子节点 }BinaryTreeNode; //为树的当前节点添加左子节点 int addLeftChild(BinaryTreeNode* curNode, char leftData) { //分配新节点 BinaryTreeNode* leftNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 leftNode->data = leftData; //新节点暂时无子节点 leftNode->left = NULL; leftNode->right = NULL; //将新节点挂到当前节点下 curNode->left = leftNode; return 1; } //为树的当前节点添加右子节点 int addRightChild(BinaryTreeNode* curNode, char rightData) { //分配新节点 BinaryTreeNode* rightNode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); //为新节点挂载数据 rightNode->data = rightData; //新节点暂时无子节点 rightNode->left = NULL; rightNode->right = NULL; //将新节点挂到当前节点下 curNode->right = rightNode; return 1; } // 队列结构体 struct Queue { BinaryTreeNode element[QUEUE_LENGTH];//队列元素应该是节点指针 int head;//头部位置 int tail;//尾部位置 }; //入队 int queueIn(struct Queue* p, BinaryTreeNode *node) { //满了 if (p->tail>QUEUE_LENGTH - 1) { return 0;//入队失败 } p->element[p->tail] = *node; p->tail++; return 1; } //出队 int queueOut(struct Queue* p, BinaryTreeNode *node) { if (p->head == p->tail) return 0;//出队失败 *node = p->element[p->head++]; return 1; } // 层序遍历 void leverOrder(struct Queue* queue) { struct Queue newQueue; newQueue.head = 0; newQueue.tail = 0; //上一级出队 BinaryTreeNode *result=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));; while (queueOut(queue, result) == 1) { printf("%c", result->data); //将子节点先加入队列，后续再遍历更深的层次 if (result->left != NULL) { queueIn(&newQueue, result->left); } if (result->right != NULL) { queueIn(&newQueue, result->right); } } leverOrder(&newQueue); } //----------------------------------------------------------------------------------------------------测试入口区域 int main() { //初始化队列 struct Queue queue; queue.head = 0; queue.tail = 0; //设定根节点 BinaryTreeNode root; //根节点A root.data = 'A'; addLeftChild(&root, 'B'); addRightChild(&root, 'C'); //为B节点增加子节点 addLeftChild(root.left, 'D'); addRightChild(root.left, 'E'); //为C节点增加子节点 addLeftChild(root.right, 'F'); addRightChild(root.right, 'G'); //为D节点增加子节点 BinaryTreeNode *b = root.left; addLeftChild(b->left, 'H'); addRightChild(b->left, 'I'); //为E节点增加子节点 addRightChild(b->right, 'K'); //为F节点增加子节点 BinaryTreeNode *c = root.right; addLeftChild(c->left, 'L'); addRightChild(c->left, 'M'); printf("\n层序遍历："); //根节点第一个进入队列 queueIn(&queue, &root); leverOrder(&queue); return 1; }
