1. 导言

    这是我写的第二篇博客，同时我也迎来了国庆最后一天的假期，又要早八了:sweat:，今天开始尝试用Markdowm完成剩余代码的见解与说明。

    • 引入

    • 层序遍历是一种广度优先的遍历方式，它按照树的层次，从上到下、从左到右依次访问每个节点。

      为了实现这种‘先访问同一层的所有节点，再进入下一层的顺序，我们需要借助**队列（FIFO）**这种数据结构：

      1. 先将根节点放入队列
      2. 每次从队列中取出一个节点并访问
      3. 然后将该节点的左右孩子（如果存在）依次入队
      4. 重复上述过程，直到队列为空 这样就能保证每一层的节点按顺序被访问到

  2. 队列的完善

    上篇文章中我们完成了二叉树的构建，接下来便可以来到第二部分 队列代码的实现

    #define max 100

struct queue
{
    struct tree_node*data[max];
    int front;
    int rear;
}；
    • 创建与初始化

    构建一个队列

    #include<stdlib>
int main(){
    queue*p=(queue*)malloc(sizeof(queue));
    void queue_init(p);
}

    初始化

    void queue_init(queue*p)
{
    p->front=0;
    p->rear=0;
}

    让 front 与rear 同时指向首元素位置，为我们后续移动确定起点

    • 入队与出队

    有了一个队列接下来便要考虑如何将二叉差树中的元素录入

    构建函数enter_queue与dequeue

    其中dequeue并不是简单的出队，还需要返回出队的元素

    void enter_queue(queue*p,tree_node*root)//这里只用传递一级指针，因为我们并不用改变该一级指针
{
    p->data[p->rear]=root;
    p->rear=(p->rear+1)%100;
}
tree_node* dequeue (queue*p)
{
    tree_node*mark=p->data[p->front];
    p->front=(p->front+1)%100;
    return mark;
}

  1. 判断queue是否为空

    int is_empty(queue*p)
{
    if((p->front+1)%max==rear)
    {
        return 1;
    }
    return 0;
}

  2. 构建主函数

    完成了树与队列的构建，准备工作就已经完成了，接下来便是主函数的构建

int main()
{
    ....
        enter_queue(p,root);
    while(!is_empty(p))//如果队列不为空，便一直循环
    {
        tree_node* current_node=dequeue(p);//将顶层的元素出队并记录
        printf("%d",current——node->data);//打印顶层元素
        if(current->left!=NULL)
        {
            enter_queue(p,current_node->left);//如果存在左孩子，便将该出队元素的左孩子入队，也就是下一层元素
        }
        if(current->right!=NULL)
        {
            enter_queue(p,current_node->right);//如果存在右孩子，便将该出队元素的右孩子入队
        }
    }
}

接下来我来手动遍历以更好理解

    A
   / \
  B   C
 / \   \
D  E   F

先将A放入队列，再将其出列，记录A，并打印

此时第一层打印完毕，队列无任何元素

然后将B，C入队

然后再用B重复A的行为

因为先入先出B之后便是C

C再次重复A的行为

以此类推 我们就打印了一层层元素

那么到此代码的总体思路便完成了，可能有些缺陷，但我已经尽力了

接下来我可能写一些历年考研数据结构代码题，一周至少写一题

有什么缺点，可以告诉我改正！