树：二叉树的层序遍历算法（超简洁实现及详细分析）

た入场券 2022-05-31 13:12 56阅读 0赞

# 实现思路 #

我们来**看看下图的二叉链表 如何实现层序遍历**。

![20180226001828381][]

层序遍历顺序：ABECDG  
A为B、E的双亲结点，遍历顺序是 根->左->右 是不是。  
而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队，出队时将其左右孩子入队，循环队列进行出队，每次出队将其左右孩子入队。当队列为空时，整棵树层序遍历完毕。还没明白请看下面过程。  
**A->出队  
队列：E、B  
B->出队  
队列：D、C、E  
E->出队  
队列：G、D、C  
C->出队  
队列：G、D  
D->出队  
队列：G  
G->出队  
队列为空，层序遍历完毕**。

# 二叉树层序遍历算法代码 #

## 层序遍历函数 ##

**层序遍历核心代码，利用了一个自己底层封装的顺序队列。如果想知道怎么实现的呢，请看[线性表：顺序队列算法实现][Link 1]**。

//一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }

## 完整代码 ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    typedef char ElemType;
    typedef struct BiNode
    {
    	ElemType data;
    	struct BiNode* lchild;
    	struct BiNode* rchild;
    }BiNode, *BiTree;
    
    //创建二叉链表
    void CreateBiTree(BiTree* tree) 
    {
    	char c;
    	scanf("%c", &c);
    	if (c == ' ')
    	{
    		*tree = NULL;
    		return;
    	}
    	*tree = malloc(sizeof(BiNode));
    	(*tree)->data = c;
    	CreateBiTree(&(*tree)->lchild);
    	CreateBiTree(&(*tree)->rchild);
    	return;
    }
    //二叉链表 递归前序遍历
    void PreTraverse(BiTree tree)
    {
    	if (tree == NULL)
    	{
    		return;
    	}
    	printf("%c ", tree->data);
    	PreTraverse(tree->lchild);
    	PreTraverse(tree->rchild);
    }
    
    //一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请前序遍历输入结点：");
    	CreateBiTree(&tree);
    	printf("前序遍历：");
    	PreTraverse(tree);
    	printf("\n层序遍历：");
    	SeqTraverse(tree);
    	
    	return 0;
    }

# 代码运行检测 #

我们构建如下图的二叉树，注意创建二叉树输入序列为：**ABC\_\_D\_\_E\_G\_\_**，\_代表一个空格哟。

![20180226002656792][]

## 运行结果 ##

![20180226002806716][]

[20180226001828381]: /images/20220531/ca8623f09efa40daaad1485df6eaa070.png
[Link 1]: https://blog.csdn.net/qq_29542611/article/details/79372198
[20180226002656792]: /images/20220531/58259c3310b84ed184cd729cf1390ca1.png
[20180226002806716]: /images/20220531/19a333676952410c92ae068e58c528cf.png