二叉树的层次遍历-C语言-数据结构

二叉树的层次遍历  

在二叉树的建立与遍历之上，利用队列的特点（先进先出），使用队列，存储二叉树的节点。

定义结构体：

在二叉树的建立之上，引入了队列

//定义结构体TreeNode
typedef struct TreeNode{
	char data;//数据域
	struct TreeNode* lchild;//指针域 ,左子树 
	struct TreeNode* rchild;//指针域 ,右子树 
}TreeNode; //为结构体起名字TreeNode

//定义结构体QueueNode
typedef struct QueueNode{
	TreeNode* data;//数据域
	struct QueueNode *pre;
	struct QueueNode *next;
}QueueNode; //为数据结构起名字QueueNode

建立二叉树，遍历二叉树 不变：

//建立树，建立过程中需要改变TreeNode里面的值 
//因为需要改变T的值，所以TreeNode *T传入形参，并不能改变T的值，所以应该使用二级指针
//采用递归算法 
void createTree(TreeNode **T,char *m,int *index){//m指针类数组，index为数组索引值 
	char mm;
	mm=m[*index];//给mm赋值字符串 
	*index+=1;//改变索引index的值
	 
	if(mm == '#'){//#时，树的节点为空节点时 
		*T=NULL;// 
	}else{//树的节点 不为空节点时  
		*T =(TreeNode*)malloc(sizeof(TreeNode));//为*T建立空间
		(*T)->data= mm;//给 *T->data 赋值字符串 mm，插入树的一个节点 
		//采用前序，插入树 
		createTree(& ((*T)->lchild),m,index);//采用递归算法 //建立左子树 
		createTree(& ((*T)->rchild),m,index);//采用递归算法 //建立右子树 
	}
} 

//遍历二叉树，并且使用前序法，输出
//采用递归算法 
void preprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		printf("%c ",T->data);//输出，一个节点 
		preprintl(T->lchild);//采用递归算法,输出左子树
		preprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

对于队列，需要对队列进行初始化，队列的入队，队列的出队。

队列进行初始化：对于二叉树的层次遍历，需要定义一个双向队列。

//初始化队列的头结点,循环队列 
QueueNode *initQueue(){
	//开辟动态空间，定义一个 Node类型的list 
	QueueNode *Q=(QueueNode*)malloc(sizeof(QueueNode));//为头结点开辟空间 
	Q->data=NULL;	//初始化时，list的数据域为0
	Q->next=Q;//初始化时，list的下一个为NULL
	Q->pre=Q;
	return Q;	//返回list链表 
}

 队列的入队：采用尾插法

队列头结点Q.......最后一个节点（Q->pre）-------------------------->队列头结点Q        形成循环

                                                                     新节点node（插入）

//pre指向前节点，next指向后节点。

最后一个节点<-node

node->队列头结点Q   

最后一个节点->node

node<-队列头结点Q   

//向队列里插入树，尾插法 
void enQueue(TreeNode *data,QueueNode *Q){//树data，队列Q 
	//开辟空间
	QueueNode *node=(QueueNode*)malloc(sizeof(QueueNode));//为新的数据，开辟空间作为新的节点  
	node->data=data;//赋值，将树data赋值给队列新节点node
	//新节点node，队列头结点Q 
	node->pre=Q->pre; //最后节点<-node
	node->next=Q;//node->Q
	Q->pre->next=node;//Q->pre为最后一个节点  //最后节点->node 
	Q->pre=node; //Q->pre为最后一个节点,为node   //node<-Q
}

队列的出队：从队列的头部出

出队列，出队列需要判断队列是否为空

队列头结点Q------>1节点------->2节点 ......最后一个节点（Q->pre）//需要删除node，也就是1节点 

//队列头结点Q不存储数据。

队列头结点Q<-2节点 

队列头结点Q->2节点

//出队列，出队列需要判断队列是否为空
//判断队列是否为空
int iskong(QueueNode *Q){
	if(Q->next==Q){
		return 1;//队列为空
	}else{
		return 0;//队列不为空
	}
} 

//出队列，从队列头部出。//尾部入，头部出
QueueNode *deQueue(QueueNode *Q){
	if(iskong(Q)){
		printf("出队列失败，队列为空\n");//输出
		return NULL;//队列为空
	}else{//队列不为空,出队列 
		QueueNode *node=Q->next;//保存第一个数据节点 
		//队列头结点Q->1节点->2节点 //需要删除node，也就是1节点 
		Q->next->next->pre=Q;//Q->next->next 是2节点，队列头结点Q<-2节点 
		Q->next=Q->next->next;// //Q->next->next 是2节点，Q->2节点
		//printf("出队列成功\n");//输出
		return node; 
	}
} 

最后，也是最重要的一部分是：将队列与树相结合

 在while循环里面

在出队列同时，插入出队列节点的左，右子节点。

//运行
void run(QueueNode *Q,TreeNode *data){
	//向队列里插入一个树的节点
	enQueue(data,Q);
	
	while(!iskong(Q)){//队列不为空时 
		QueueNode *node=deQueue(Q);//出队列，出队列的头一个数据节点
		printf("%c ",node->data->data);//node->data是队列里面的TreeNode* data表示树，node->data->data是树里面的 char data;//数据域
		if(node->data->lchild){//如果树的，左子节点，不为空 ，将 左子节点 插入队列 
			//向队列里插入一个树的，左子节点 
			enQueue(node->data->lchild,Q);
		} 
		if(node->data->rchild){//如果树的，右子节点，不为空 ，将 右子节点 插入队列 
			//向队列里插入一个树的，右子节点 
			enQueue(node->data->rchild,Q);
		}  
	} //退出循环 
}

总代码：

#include<stdio.h>
#include<stdlib.h>		//开辟空间所需要的头文件 

//定义结构体TreeNode
typedef struct TreeNode{
	char data;//数据域
	struct TreeNode* lchild;//指针域 ,左子树 
	struct TreeNode* rchild;//指针域 ,右子树 
}TreeNode; //为结构体起名字TreeNode

//定义结构体QueueNode
typedef struct QueueNode{
	TreeNode* data;//数据域
	struct QueueNode *pre;
	struct QueueNode *next;
}QueueNode; //为数据结构起名字QueueNode


//建立树，建立过程中需要改变TreeNode里面的值 
//因为需要改变T的值，所以TreeNode *T传入形参，并不能改变T的值，所以应该使用二级指针
//采用递归算法 
void createTree(TreeNode **T,char *m,int *index){//m指针类数组，index为数组索引值 
	char mm;
	mm=m[*index];//给mm赋值字符串 
	*index+=1;//改变索引index的值
	 
	if(mm == '#'){//#时，树的节点为空节点时 
		*T=NULL;// 
	}else{//树的节点 不为空节点时  
		*T =(TreeNode*)malloc(sizeof(TreeNode));//为*T建立空间
		(*T)->data= mm;//给 *T->data 赋值字符串 mm，插入树的一个节点 
		//采用前序，插入树 
		createTree(& ((*T)->lchild),m,index);//采用递归算法 //建立左子树 
		createTree(& ((*T)->rchild),m,index);//采用递归算法 //建立右子树 
	}
} 

//遍历二叉树，并且使用前序法，输出
//采用递归算法 
void preprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		printf("%c ",T->data);//输出，一个节点 
		preprintl(T->lchild);//采用递归算法,输出左子树
		preprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

//初始化队列的头结点,循环队列 
QueueNode *initQueue(){
	//开辟动态空间，定义一个 Node类型的list 
	QueueNode *Q=(QueueNode*)malloc(sizeof(QueueNode));//为头结点开辟空间 
	Q->data=NULL;	//初始化时，list的数据域为0
	Q->next=Q;//初始化时，list的下一个为NULL
	Q->pre=Q;
	return Q;	//返回list链表 
}

//向队列里插入树，尾插法 
void enQueue(TreeNode *data,QueueNode *Q){//树data，队列Q 
	//开辟空间
	QueueNode *node=(QueueNode*)malloc(sizeof(QueueNode));//为新的数据，开辟空间作为新的节点  
	node->data=data;//赋值，将树data赋值给队列新节点node
	//新节点node，队列头结点Q 
	node->pre=Q->pre; //最后节点<-node
	node->next=Q;//node->Q
	Q->pre->next=node;//Q->pre为最后一个节点  //最后节点->node 
	Q->pre=node; //Q->pre为最后一个节点,为node   //node<-Q
}

//出队列，出队列需要判断队列是否为空
//判断队列是否为空
int iskong(QueueNode *Q){
	if(Q->next==Q){
		return 1;//队列为空
	}else{
		return 0;//队列不为空
	}
} 

//出队列，从队列头部出。//尾部入，头部出
QueueNode *deQueue(QueueNode *Q){
	if(iskong(Q)){
		printf("出队列失败，队列为空\n");//输出
		return NULL;//队列为空
	}else{//队列不为空,出队列 
		QueueNode *node=Q->next;//保存第一个数据节点 
		//队列头结点Q->1节点->2节点 //需要删除node，也就是1节点 
		Q->next->next->pre=Q;//Q->next->next 是2节点，队列头结点Q<-2节点 
		Q->next=Q->next->next;// //Q->next->next 是2节点，Q->2节点
		//printf("出队列成功\n");//输出
		return node; 
	}
} 

//运行
void run(QueueNode *Q,TreeNode *data){
	//向队列里插入一个树的节点
	enQueue(data,Q);
	
	while(!iskong(Q)){//队列不为空时 
		QueueNode *node=deQueue(Q);//出队列，出队列的头一个数据节点
		printf("%c ",node->data->data);//node->data是队列里面的TreeNode* data表示树，node->data->data是树里面的 char data;//数据域
		if(node->data->lchild){//如果树的，左子节点，不为空 ，将 左子节点 插入队列 
			//向队列里插入一个树的，左子节点 
			enQueue(node->data->lchild,Q);
		} 
		if(node->data->rchild){//如果树的，右子节点，不为空 ，将 右子节点 插入队列 
			//向队列里插入一个树的，右子节点 
			enQueue(node->data->rchild,Q);
		}  
	} //退出循环 
}

//主函数
int main(){
	TreeNode *T;//定义一个树结构体T 
	int index=0;//索引设为0 
	char *m="ABC##D##EF##G##";
	//创建树
	createTree(&T,m,&index);
	//遍历二叉树，并且使用前序法，输出
	preprintl(T);
	printf("\n");
	//初始化队列
	QueueNode* Q=initQueue();
	//运行
	run(Q,T);
}