二叉树层次遍历--C语言

拼搏现实的明天。 2022-04-03 10:12 201阅读 0赞

之前写了二叉树的先序、中序、后序遍历，这些遍历都用到了栈结构。今天写一下二叉树的层次遍历，层次遍历用到的数据结构是队列。  
  层次遍历算法中增加了三个int型数据，其中levelcount用于记录现在处理的是树的第几层；curlevel用于记录当前层还有几个节点没有被访问过；nextlevel用于记录本层的下一层的节点数。  
代码如下：

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    #define INITQUEUE 20
    
    typedef struct BiTNode
    {
        
    	char data;//节点数据
    	struct BiTNode *lchild;//节点左孩子指针
    	struct BiTNode *rchild;//节点右孩子指针
    }BiTNode,*BiTree;//二叉树节点
    
    typedef struct Queue
    {
        
    	BiTNode *front;//队列头指针
    	BiTNode *tail;//队列尾指针
    	int size;//队列空间大小
    }Queue;
    
    //创建队列
    int InitQueue(Queue &Q)
    {
        
    	Q.front = (BiTNode*)malloc(INITQUEUE * sizeof(BiTNode));
    	if(!Q.front)
    	{
        
    		return 0;
    	}
    	Q.tail = Q.front;
    	Q.size = INITQUEUE;
    	return 1;
    }
    
    //判断队列是否为空
    bool EmptyQueue(Queue Q)
    {
        
    	if(Q.tail == Q.front)
    	{
        
    		return true;
    	}
    	else
    	{
        
    		return false;
    	}
    }
    
    //入队列
    int EnQueue(Queue &Q,BiTNode e)
    {
        
    	if((Q.tail - Q.front + INITQUEUE) % INITQUEUE == INITQUEUE - 1)
    	{
        
    		return 0;
    	}
    	*Q.tail = e;
    	Q.tail++;
    	return 1;
    }
    
    //出队列
    int DeQueue(Queue &Q,BiTNode &e)
    {
        
    	if(Q.front == Q.tail)
    	{
        
    		return 0;
    	}
    	e = *Q.front;
    	Q.front++;
    	return 1;
    }
    
    //创建二叉树
    void CreateBiTree(BiTree &T)
    {
        
    	char ch;
    	scanf("%c",&ch);
    	if('#' == ch)
    	{
        
    		T = NULL;
    	}
    	else
    	{
        
    		T = (BiTree)malloc(sizeof(BiTNode));
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    
    //二叉树的层次遍历
    int levelTraverse(BiTree T)
    {
        
    	if(NULL == T)
    	{
        
    		return 0;
    	}
    	BiTNode e;
    	Queue Q;
    	int levelcount = 0;//树的深度
    	int curlevel = 1;//本层剩余的未访问的节点数
    	int nextlevel = 0;//下一层未访问的节点数
    	InitQueue(Q);
    	EnQueue(Q,*T);
    	while(!EmptyQueue(Q))
    	{
        
    		DeQueue(Q,e);
    		printf("%c ",e.data);
    		curlevel--;
    		if(NULL != e.lchild)
    		{
        
    			EnQueue(Q,*e.lchild);
    			nextlevel ++;
    		}
    		if(NULL != e.rchild)
    		{
        
    			EnQueue(Q,*e.rchild);
    			nextlevel++;
    		}
    		if(0 == curlevel)
    		{
        
    			levelcount++;
    			printf("第%d层节点遍历结束!\n",levelcount);
    			curlevel = nextlevel;
    			nextlevel =0;
    		}
    	}
    	return 1;
    }
    
    int main(int argc, char* argv[])
    {
        
    	BiTree T = NULL;
    	CreateBiTree(T);
    	levelTraverse(T);
    	return 0;
    }

二叉树的结构为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]

遍历结果：  
![在这里插入图片描述][20181221175109496.png]  
  二叉树的遍历基本上已经写过一遍了，有机会需要写一个二叉树的总结。当然现在写的都还只是二叉树的皮毛的东西，像二叉树的一些应用（平衡二叉树、红黑树等）都还没有写。但是这些东西需要先把理论弄清楚，才能着手去写，要不然思路不清晰，写出来的代码必然是不能看的！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_16_color_FFFFFF_t_70]: /images/20220403/c5729a89554e4b59a98bc64b7fd8b949.png
[20181221175109496.png]: /images/20220403/727bac61760744aabe0124e8af8df022.png