C语言二叉树的层序遍历

在上一篇中我记录了二叉树的先序，中序，后序的递归和非递归遍历方法，这一篇会接着上一篇的，记录二叉树的层序遍历方法，层序遍历用到了队列的数据结构，下面直接上代码：

1、首先是链队列的数据结构定义，LinkQueue.h文件：

#pragma once
#include "BinaryTree.h"

/** 链队列的节点定义，包含一个数据域和下一个节点的指针 */
typedef struct QueueNode {
BiTreeNode* data;
struct QueueNode* next;
}QueueNode;

/**  链队列的定义，包含队头和队尾指针*/
typedef struct {
QueueNode* front;
QueueNode* rear;
}LinkQueue;

LinkQueue* InitQueue();/** 链队列的初始化 */
void DestoryQueue(LinkQueue*);/** 销毁队列 */
void EnQueue(LinkQueue*, BiTreeNode*);/** 入队 */
BiTreeNode* DeQueue(LinkQueue*);/** 出队 */

2、LinkQueue.c文件：

#include <stdio.h>
#include <stdlib.h>
#include "LinkQueue.h"

/** 链队列的初始化 */
LinkQueue* InitQueue()
{
LinkQueue* queue = (LinkQueue*)malloc(sizeof(LinkQueue));
if (!queue)
{
printf("init queue error!\n");
exit(0);
}
queue->front = (QueueNode*)malloc(sizeof(QueueNode));
queue->front->next = NULL;
queue->rear = queue->front;
return queue;
}

/** 链队列的销毁，注意先进去的是队列头，后进去的是队列尾 */
void DestoryQueue(LinkQueue* queue)
{
while (queue->front)
{
queue->rear = queue->front->next;
free(queue->front);
queue->front = queue->rear;
}
}

/** 入队 */
void EnQueue(LinkQueue* queue, BiTreeNode* node)
{
QueueNode* queueNode = (QueueNode*)malloc(sizeof(QueueNode));
queueNode->data = node;
queueNode->next = NULL;
queue->rear->next = queueNode;
queue->rear = queueNode;
}

/** 出队 */
BiTreeNode* DeQueue(LinkQueue* queue)
{
if (queue->front == queue->rear)//队列为空
return NULL;
QueueNode* p = queue->front->next;
BiTreeNode* node = p->data;
queue->front = p;
return node;
}

3、层序遍历的主要代码

void LayerOrderBiTree(struct BiTreeNode* root)
{
int curLayerCount = 0; //当前层中的节点数
int nextLayerCount = 0; //下一层中的节点数
struct Queue* queue = InitQueue();
EnQueue(queue, root);
curLayerCount++;
struct BiTreeNode* p;
while (p = DeQueue(queue))
{
curLayerCount--;
printf("%c ", p->val);
if (p->left)
{
EnQueue(queue, p->left);
nextLayerCount++;
}
if (p->right)
{
EnQueue(queue, p->right);
nextLayerCount++;
}
if (curLayerCount == 0)//一层已经遍历完毕
{
curLayerCount = nextLayerCount;
nextLayerCount = 0;
printf("\n");
}
}
}

4、测试代码

#include<stdio.h>
#include <stdlib.h>
#include "Stack.h"

void printResult(char *msg, void(*p)(BiTreeNode*), BiTreeNode* node)
{
printf("\n---------%s---------\n", msg);
p(node);
printf("\n---------%s---------\n", msg);
}

int main()
{
printf("使用先序创建二叉树，#表示空节点，请输入二叉树的数据：\n");
BiTreeNode* root = CreateBinaryTree();

printResult("层序遍历", LayerOrderBiTree, root);

return 0;
}

测试用的二叉树如下图：

代码运行结果如下图：

下面记录遇到的坑：

在实现队列的出队操作时，代码如下：

开始我的代码写错了，第46行写成了QueueNode* p = queue->front，结果运行报错，单步跟踪后发现出队不正确，后来检查原来46行代码不对，原因是初始化队列时，给对头分配了内存空间，然后对头跟队尾都指向该空间，但是入队的时候该空间是没有用到的，就相当于建立单链表时带了一个头结点，如下图所示：

所以出队的时候，队头节点应该是queue->front->next，而不是queue->front！！！

------------------------------这里是分割线-------------------------------

今天在网上看到一种递归输出层序结果的方法，记录如下，直接上所有代码：

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct Node {
char val;
struct Node* left = NULL;
struct Node* right = NULL;
}TreeNode, *Tree;

Tree createTree() {
char c;
cin >> c;
if(c == '#') return NULL;
Tree tree = (Tree)malloc(sizeof(Tree));
tree->val = c;
tree->left = createTree();
tree->right = createTree();
return tree;
} 

void preOrder(Tree tree) {
TreeNode* p = tree;
if(p) {
cout << p->val << " ";
preOrder(p->left);
preOrder(p->right);
}
}

//打印第level行的节点，有打印输出则返回true，否则返回false 
bool printLevel(Tree tree, int level) {
if(!tree || level < 0) {
return false;
}
if(level == 0) {
cout << tree->val << " ";
return true;
}
return printLevel(tree->left, level - 1) + printLevel(tree->right, level - 1);
}

//层序遍历，当某一行没有打印时break掉循环 
void levelOrder(Tree tree) {
for(int i = 0; ; i++) {
if(!printLevel(tree, i)) {
break;
}
}
}

int main()
{
Tree tree = createTree();
cout << "pre order: " << endl;
preOrder(tree);
cout << "\nlevel order: " << endl;
levelOrder2(tree);
return 0;
}

所用二叉树为：

测试结果如下图：

递归的代码比非递归简单，但是复杂度可能就没有非递归那么低了