数据结构与算法之二叉树的层序遍历

• 什么是层序遍历
• • 算法思想
  • • 动图展示
    • 代码展示
    • • 头文件
      • • `BiTNodeSqQueue.h`
        • `BiTNode.h`

首先，看下图

层序遍历结果应该是：ABCDEFGHIJKL

1. 初始化一个辅助队列
2. 根节点入队
3. 若队列非空，则队头节点出队，访问该节点，并将其左、右孩子插入队尾(如果有的话)
4. 重复3直至队列为空

void levelOrder(BiTree biTree) {
    //初始化一个队列
    BiTNodeSqQueue *queue;
    initBiTNodeSqQueue(&queue);
    //添加根元素之队列
    enBiTNodeSqQueue(queue, *biTree);
    //用于保留出队元素
    BiTNode *deBiNode;
    while (emptyBiTNodeSqQueue(queue)) {
        //队列出队
        deBiTNodeSqQueue(queue, deBiNode);
        printf("%dt", deBiNode->data);
        //将出队元素的左右子树添加至队列
        if (NULL != deBiNode->lChild) {
            enBiTNodeSqQueue(queue, *deBiNode->lChild);
        }
        if (NULL != deBiNode->rChild) {
            enBiTNodeSqQueue(queue, *deBiNode->rChild);
        }
    }
    printf("%dt", biTree->data);
}

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#include "BiTNode.h"

#define MAXSIZE 3 //最大长度
typedef struct {
    BiTNode *data[MAXSIZE];  //静态数组
    int front; //队头
    int rear;  //队尾
    
    int tag;  //记录操作，0为入队，1为出队
} BiTNodeSqQueue;


bool initBiTNodeSqQueue(BiTNodeSqQueue **queue) {
    *queue = (BiTNodeSqQueue *) malloc(sizeof(BiTNodeSqQueue));
    if (*queue == NULL) {
        return false;
    }
    (*queue)->front = 0;
    (*queue)->rear = 0;
    (*queue)->tag = 1;
    return true;
}


bool emptyBiTNodeSqQueue(BiTNodeSqQueue *queue) {
    if (NULL == queue) {
        return true;
    }
    if (queue->front == 0) {
        return true;
    }
    return false;
}


bool enBiTNodeSqQueue(BiTNodeSqQueue *queue, BiTNode *data) {
    if (queue == NULL) {
        return false;
    }
    int i = (queue->rear + 1) % MAXSIZE;
    if (queue->rear == queue->front && queue->tag == 0) {
        return false;
    }
    queue->data[queue->rear] = data;
    queue->rear = i;
    queue->tag = 0;
    return true;
}


bool deBiTNodeSqQueue(BiTNodeSqQueue *queue, BiTNode **e) {
    if (queue == NULL) {
        return false;
    }
    if (queue->rear == queue->front && queue->tag == 1) {
        return false;
    }
    *e = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAXSIZE;
    queue->tag = 1;
    return true;
}

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

typedef struct BiTNode {
    int data;
    struct BiTNode *lChild;
    struct BiTNode *rChild;
} BiTNode, *BiTree;



bool initTNode(BiTNode **biTNode) {
    (*biTNode) = (BiTNode *) malloc(sizeof(BiTNode));
    if (NULL == (*biTNode)) {
        false;
    }
    (*biTNode)->lChild = NULL;
    (*biTNode)->rChild = NULL;
    return true;
}


void preOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    printf("%dt", biTree->data);
    //左子树，因为子树和根都是一样的数据结构所以可以直接递归
    preOrder(biTree->lChild);
    //右子树，因为子树和根都是一样的数据结构所以可以直接递归
    preOrder(biTree->rChild);
}


void midOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    //左子树，因为子树和根都是一样的数据结构所以可以直接递归
    midOrder(biTree->lChild);
    //根节点data打印
    printf("%dt", biTree->data);
    //右子树，因为子树和根都是一样的数据结构所以可以直接递归
    midOrder(biTree->rChild);
}


void postOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    //左子树，因为子树和根都是一样的数据结构所以可以直接递归
    postOrder(biTree->lChild);
    //右子树，因为子树和根都是一样的数据结构所以可以直接递归
    postOrder(biTree->rChild);
    //根节点data打印
    printf("%dt", biTree->data);
}