数据结构笔记——二叉树的层序遍历

淩亂°似流年 2023-02-13 08:04 28阅读 0赞

**目录**

一、二叉树的层序遍历

二、代码实现

三、总结

## **一、二叉树的层序遍历** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

![20200527213523283.png][]

算法思想：

①初始化一个辅助队列

②根结点入队

③若队列非空，则队头结点出队，访问该结点，将其左右孩子插入队尾（如果有的话）

④重复③直至队列为空

## **二、代码实现** ##

//层序遍历
    void LevelOrder(BiTree T){
        LinkQueue Q;
        InitQueue(Q);    //初始化辅助队列
        BiTree p;
        EnQueue(Q,T);        //将根结点入队
        while(!IsEmpty(Q)){    //队列不空则循环
            DeQueue(Q,p);        //队头结点出队
            visit(p);        //访问出队结点
            if(p->lchild != NULL)
                EnQueue(Q,p->lchild);    //左孩子入队
            if(p->rchild != NULL)
                EnQueue(Q,p->rchild);    //右孩子入队
        }
    }
    
    //二叉树的结点（链式存储）
    typedef struct BiTNode{
        char data;
        struct BiTNode *lchild,rchild;
    }
    
    //链式队列结点
    typedef struct LinkNode{
        BiTNode * data;    //存指针而不是结点
        struct LinkNode *next;
    }
    
    typedef struct{
        LinkNode *front,*rear;
    }LinkQueue;

## **三、总结** ##

![20200527214708751.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527213320225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200527213523283.png]: https://img-blog.csdnimg.cn/20200527213523283.png
[20200527214708751.png]: https://img-blog.csdnimg.cn/20200527214708751.png