C语言实现二叉树的层次遍历

浅浅的花香味﹌ 2023-03-02 05:09 33阅读 0赞

#  #

## 1. **基本思路** ##

进行层次遍历时构建一个辅助队列，先将二叉树根节点入队，然后出队，访问出队结点，若它有左子树，将左子树根节点入队，然后出队，访问出队结点…，右子树也同样如此，循环往复直到队列为空。

## 2.代码 ##

#include<stdio.h>
    #include <malloc.h>
    //二叉树的链式存储结构
    typedef struct BiTNode {
        
    	char data;
    	struct BiTNode* lchild, * rchild;
    }BiTNode, * BiTree;
    
    //链式队列，存放二叉树结点
    typedef struct QNode {
        
        BiTNode* data;
    	struct QNode* next;
    }QNode, * QueuePtr;
    
    //队列头指针、尾指针
    typedef struct {
        
    	QueuePtr front; 
    	QueuePtr rear;
    }LinkQueue;
    
    
    //初始化队列
    void InitQueue(LinkQueue& Q) {
        
    	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    	Q.front->next = NULL;   //头结点
    	if (Q.front)
    		printf("队列初始化成功\n");
    }
    //入队
    void EnQueue(LinkQueue& Q, BiTree B) {
        
    	QNode* q = (QueuePtr)malloc(sizeof(QNode));//要入队列的节点
    	q->data = B;
    	q->next = NULL;
    	Q.rear->next = q;
    	Q.rear = q;
    }
    //出队
    BiTree DeQueue(LinkQueue& Q,BiTree &B) {
        
    	QueuePtr p =  Q.front->next;      //出队的节点
    	B = p->data;
    	Q.front->next = p->next;
    	if (Q.rear==p)
    		Q.front = Q.rear;
    	free(p);
    	return B;
    }
    bool IsEmpty(LinkQueue Q) {
        
    	if (Q.front == Q.rear)
    		return true;
    	else
    		return false;
    }
    //创建树
    BiTree CreatBi() {
        
    	char x;
    	BiTree B = (BiTree)malloc(sizeof(BiTNode));
    	scanf_s("%c",&x);
    	printf("%c", x);
    	if (x!='.') //输入“.”表示空
    	{
        
    		B->data = x;
    		B->lchild = CreatBi();
    		B->rchild = CreatBi();
    	}
    	else
    		B = NULL;
    	return B;
    }
    
    int main() {
        
    	//1.创建树
    	BiTree b = CreatBi();
    	//2.初始化辅助队列
    	LinkQueue lq;
    	InitQueue(lq);
    	//3.头结点入队
    	EnQueue(lq,b);
    	BiTree temp;
    	//4.遍历
    	while (!IsEmpty(lq))
    	{
        
    	//4.1 头结点出队
    		temp = DeQueue(lq, b);
    	//4.2 访问出队结点
    		printf("%c",temp->data);
    	//4.3 左子树根节点入队
    		if (temp->lchild != NULL)
    			EnQueue(lq,temp->lchild);
    	//4.4 右子树根节点入队
    		if (temp->rchild != NULL)
    			EnQueue(lq, temp->rchild);	
    	}
    
    	return 0;
    }

## 3.结果和分析 ##

（1）对下图二叉树进行层次遍历  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMzNzYzNw_size_16_color_FFFFFF_t_70_pic_center][]（2）运行结果

![在这里插入图片描述][20200727211421630.png_pic_center]  
(3)分析  
二叉树的层序遍历实现较为简单，主要需要构建一个辅助队列，了解队列和树的一些基础操作；因为实现的功能较为简单，我这里一些队列的操作不是很完善，有需要可以自行添加。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMzNzYzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/c242b1059b3f49acb5434505f820e099.png
[20200727211421630.png_pic_center]: /images/20230208/db32136d7a014bbaa7e38885736aa550.png