# 二叉树层序遍历学习与实现记录 ## v0.1 2025.10.8

[GCMG666]

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;
}

3. 判断queue是否为空

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

4. 构建主函数

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

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的行为

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

---

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

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

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