[数据结构与算法]二叉树的层次遍历算法的实现

借助队列实现层次遍历：
binary_tree.h

#ifndef _LINK_QUEUE_H
#define _LINK_QUEUE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define QUEUE_ERR (-1)
#define QUEUE_SUCCESS 0
#define QUEUE_MAX_SIZE 128
#define BIN_TREE_ERR (-1)
#define BIN_TREE_SUCCESS 0

typedef struct binary_node{
    char nodeValue;
    struct binary_node *leftChild;
    struct binary_node *rightChild;
}*PBinTree, BinTree;

typedef PBinTree DataType;

typedef struct link_queue_node {
    DataType data;
    struct link_queue_node *next;
}*PQueueNode, QueueNode;

typedef struct link_queue {
    PQueueNode front;
    PQueueNode rear;
    int size;
}*PQueue, Queue;

/* 创建一个队列 */
PQueue CreateQueue();
/* 获取一个队列的长度 */
int GetQueueLength(const PQueue queue);
/* 判断一个队列是否为空 */
int QueueIsEmpty(const PQueue queue);
/* 向队列尾部插入一个数据 */
int InsertToQueueRear(PQueue queue, const DataType data);
/* 将队首元素出队列 */
int DeleteFromQueueFront(PQueue queue);
/* 获取队列头部元素而不出列 */
DataType GetFrontElement(const PQueue queue);
/* 将一个队列清空 */
void ClearQueue(PQueue queue);
/* 销毁一个队列 */
void DestroyQueue(PQueue queue);

/* 递归创建一个二叉树 */
void CreateBinTree(PBinTree *tree);
/* 层次遍历 */
void LevelTraverTree(PBinTree tree);

#endif

bianry_tree.c

#include "link_queue.h"

PQueue CreateQueue()
{
    PQueue queue = (PQueue)malloc(sizeof(Queue));
    if(queue == NULL) {
        perror("queue malloc error.");
        return (PQueue)QUEUE_ERR;
    }
    queue->front = queue->rear = NULL;
    queue->size = 0;
    return queue;
}

int GetQueueLength(const PQueue queue)
{
    if(queue == NULL) {
        perror("queue malloc error.");
        return QUEUE_ERR;
    }
    return queue->size;
}

int QueueIsEmpty(const PQueue queue)
{
    if(queue == NULL) {
        perror("queue malloc error.");
        return QUEUE_ERR;
    }
    return (queue->size == 0);
}

int InsertToQueueRear(PQueue queue, const DataType data)
{
    if(queue == NULL) {
        perror("queue malloc error.");
        return QUEUE_ERR;
    }
    PQueueNode addNode = (PQueueNode)malloc(sizeof(QueueNode));
    if(addNode == NULL) {
        perror("new node malloc error.");
        return QUEUE_ERR;
    }
    addNode->data = data;
    addNode->next = NULL;
    if(QueueIsEmpty(queue)) {
        queue->front = addNode;
        queue->rear = addNode;
    } else {
        queue->rear->next = addNode;
        queue->rear = addNode;
    }
    queue->size++;
    
    return QUEUE_SUCCESS;
}

int DeleteFromQueueFront(PQueue queue)
{
    if(queue == NULL) {
        perror("queue malloc error.");
        return QUEUE_ERR;
    }
    if(queue->size == 0) {
        perror("queue is empty, no element can be deleted.");
        return QUEUE_ERR;
    }
    PQueueNode delNode = queue->front;
    queue->front = queue->front->next;
    queue->size--;
    free(delNode);
    return QUEUE_SUCCESS;  
}

DataType GetFrontElement(const PQueue queue)
{
    if(queue == NULL) {
        perror("queue malloc error.");
        return (DataType)QUEUE_ERR;
    }
    if(queue->size == 0) {
        perror("queue is empty, no element can be deleted.");
        return (DataType)QUEUE_ERR;
    }
    return queue->front->data;
}

void ClearQueue(PQueue queue)
{
    if(queue == NULL) {
        perror("queue is null.");
        return;
    }
    while(queue->size != 0) {
        DeleteFromQueueFront(queue);
    }
    return;
}

void DestroyQueue(PQueue queue)
{
    if(queue == NULL) {
        perror("queue is null.");
        return;
    }
    while(!QueueIsEmpty(queue)) {
        DeleteFromQueueFront(queue);
    }
    free(queue);
    printf("destroy queue completed.\n");
    return;
}

void CreateBinTree(PBinTree *tree)
{
    char ch;
	scanf("%c",&ch);
	if(ch == '#') {
		*tree = NULL;
	} else {
		*tree = (PBinTree)malloc(sizeof(BinTree));
		if(*tree == NULL) {
			perror("tree malloc error.");
			exit(BIN_TREE_ERR);
		}
		(*tree)->nodeValue = ch;
		CreateBinTree(&(*tree)->leftChild);
		CreateBinTree(&(*tree)->rightChild);
	}
}

void LevelTraverTree(PBinTree tree)
{
    if(tree == NULL) {
        perror("tree root is null.");
        return;
    }
    DataType temp;
    PQueue queue = CreateQueue();
    InsertToQueueRear(queue, tree);
    while(!QueueIsEmpty(queue)) {
        temp = GetFrontElement(queue);
        if(temp == (DataType)QUEUE_ERR || temp == NULL) {
            perror("get front element error.");
            return;
        } 
        printf("%c ", temp->nodeValue);
        DeleteFromQueueFront(queue);
        if(temp->leftChild != NULL) {
            InsertToQueueRear(queue, temp->leftChild);
        }
        if(temp->leftChild != NULL) {
            InsertToQueueRear(queue, temp->rightChild);
        }
    }
}

main.c

#include "link_queue.c"

int main()
{
    PBinTree myTree;
    CreateBinTree(&myTree);
    printf("create completed.\n");
    PreTraverTree(myTree);
    printf("pretrav completed.\n");
    LevelTraverTree(myTree);
    printf("leveltrav completed.\n");
    return 0;
}