1. AI技术聚合首页
  2. IT

二叉树的层次遍历（C语言）

乘风 • • IT • 阅读 51

一、二叉树的概念以及结构

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。

二、二叉树的遍历图解

先序遍历

中序遍历

 

 后序遍历

 层次遍历

 

 

 三、代码部分

一、头文件

二、二叉树的结构

三、队列的结构

四、队列的初始化

五、判断队列是否为空

六、添加元素

七、删除元素

八、创建结点

九、创建二叉树

十、层次遍历

十一、主函数

十二、全部代码

十三、测试结果

一、头文件

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 5

 

二、二叉树的结构

//二叉树的结构 
typedef struct BTnode
{
	char element;
	struct BTnode *left;
	struct BTnode *right;	
}*BTnodePtr;

 

三、队列的结构

//队列
typedef struct BTNodePtrQueue
{
	BTnodePtr *nodePtrs;
	int front;
	int rear;
}*QueuePtr;

 

四、队列的初始化

//初始化队列
QueuePtr initQueue()
{
	QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
	resultPtr->front = 0;
	resultPtr->rear = 1;
	return resultPtr;	
}

 

五、判断队列是否为空

int isQueueEmpty(QueuePtr paraQueuePtr)
{
	if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear) 
	{
		return 1;
	}

	return 0;
}

 

六、添加元素

//在队列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
	if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
	{
		printf("The queue is full.\n");
		return ; 
	}	
	Queue->nodePtrs [Queue->rear] = newBTnodePtr;
	Queue->rear = (Queue->rear+1)%MAXSIZE;
	printf("enqueue %c ends.\r\n", newBTnodePtr->element);
		
}

 

七、删除元素

 

//删除元素
BTnodePtr deQueue(QueuePtr Queue)
{
	if(isQueueEmpty(Queue))
	{
		printf("The queue is empty,can not delete.\n");
		return ;
	}
	Queue->front = (Queue->front +1)%MAXSIZE;
	printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);

	return  Queue->nodePtrs [Queue->front];
}

八、创建结点

 

//创建结点 
BTnodePtr constructBTnode(char newElement)
{
	BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
	newPtr->element = newElement;
	newPtr->left = NULL;
	newPtr->right  = NULL;
	return newPtr;
}

九、创建二叉树

 

//创建二叉树
BTnodePtr stringToBTree(char *newString)
{
	int i;
	char ch;
	i = 0;
	QueuePtr Queue = initQueue();
	
	BTnodePtr resultHeader;
	BTnodePtr tempParent,tempLeftChlid,tempRightChild;
	
	ch = newString[i];
	resultHeader = constructBTnode(ch);
	enqueue(Queue,resultHeader);
	
	while(!isQueueEmpty(Queue))
	{
		tempParent = deQueue(Queue);
		//左 
		i++;
		if(newString[i] == '#')
		{
			tempParent->left = NULL;
		}
		else
		{
			tempLeftChlid = constructBTnode(newString[i]);
			enqueue(Queue,tempLeftChlid);
			tempParent->left = tempLeftChlid;
		}
		//右
		i++;
		if(newString[i] == '#')
		{
			tempParent->right = NULL;
		}
		else
		{
			tempRightChild = constructBTnode(newString[i]);
			enqueue(Queue,tempRightChild);
			tempParent->right = tempRightChild;
		}
		
	 } 
	return resultHeader;	
}

十、层次遍历

 

//层次遍历
void levelwise(BTnodePtr newTreePtr)
{
	char string[100];
	int i = 0;
	
	QueuePtr Queue = initQueue();
	BTnodePtr tempNodePtr;
	
	enqueue(Queue,newTreePtr);
	while(!isQueueEmpty(Queue))
	{
		tempNodePtr = deQueue(Queue);
		string[i] = tempNodePtr->element ;
		i++;
		if(tempNodePtr->left != NULL)
		{
			enqueue(Queue,tempNodePtr->left);
		}
		if(tempNodePtr->right  != NULL)
		{
			enqueue(Queue,tempNodePtr->right);
		}
	}
	string[i] = '\0';
	printf("levewise:%s",string);
}

十一、主函数

 

int main(){
	BTnodePtr tempHeader;
	char* tempString = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("\r\n");

	return 1;
}

十二、全部代码

 

include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 5

//二叉树的结构 
typedef struct BTnode
{
	char element;
	struct BTnode *left;
	struct BTnode *right;	
}*BTnodePtr;
//队列
typedef struct BTNodePtrQueue
{
	BTnodePtr *nodePtrs;
	int front;
	int rear;
}*QueuePtr;
//初始化队列
QueuePtr initQueue()
{
	QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
	resultPtr->front = 0;
	resultPtr->rear = 1;
	return resultPtr;	
} 
int isQueueEmpty(QueuePtr paraQueuePtr)
{
	if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear) 
	{
		return 1;
	}

	return 0;
}
//在队列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
	if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
	{
		printf("The queue is full.\n");
		return ; 
	}	
	Queue->nodePtrs [Queue->rear] = newBTnodePtr;
	Queue->rear = (Queue->rear+1)%MAXSIZE;
	printf("enqueue %c ends.\r\n", newBTnodePtr->element);
		
} 
//删除元素
BTnodePtr deQueue(QueuePtr Queue)
{
	if(isQueueEmpty(Queue))
	{
		printf("The queue is empty,can not delete.\n");
		return ;
	}
	Queue->front = (Queue->front +1)%MAXSIZE;
	printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);

	return  Queue->nodePtrs [Queue->front];
} 
//创建结点 
BTnodePtr constructBTnode(char newElement)
{
	BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
	newPtr->element = newElement;
	newPtr->left = NULL;
	newPtr->right  = NULL;
	return newPtr;
}
//创建二叉树
BTnodePtr stringToBTree(char *newString)
{
	int i;
	char ch;
	i = 0;
	QueuePtr Queue = initQueue();
	
	BTnodePtr resultHeader;
	BTnodePtr tempParent,tempLeftChlid,tempRightChild;
	
	ch = newString[i];
	resultHeader = constructBTnode(ch);
	enqueue(Queue,resultHeader);
	
	while(!isQueueEmpty(Queue))
	{
		tempParent = deQueue(Queue);
		//左 
		i++;
		if(newString[i] == '#')
		{
			tempParent->left = NULL;
		}
		else
		{
			tempLeftChlid = constructBTnode(newString[i]);
			enqueue(Queue,tempLeftChlid);
			tempParent->left = tempLeftChlid;
		}
		//右
		i++;
		if(newString[i] == '#')
		{
			tempParent->right = NULL;
		}
		else
		{
			tempRightChild = constructBTnode(newString[i]);
			enqueue(Queue,tempRightChild);
			tempParent->right = tempRightChild;
		}
		
	 } 
	return resultHeader;	
}
//层次遍历
void levelwise(BTnodePtr newTreePtr)
{
	char string[100];
	int i = 0;
	
	QueuePtr Queue = initQueue();
	BTnodePtr tempNodePtr;
	
	enqueue(Queue,newTreePtr);
	while(!isQueueEmpty(Queue))
	{
		tempNodePtr = deQueue(Queue);
		string[i] = tempNodePtr->element ;
		i++;
		if(tempNodePtr->left != NULL)
		{
			enqueue(Queue,tempNodePtr->left);
		}
		if(tempNodePtr->right  != NULL)
		{
			enqueue(Queue,tempNodePtr->right);
		}
	}
	string[i] = '\0';
	printf("levewise:%s",string);
} 

int main(){
	BTnodePtr tempHeader;
	char* tempString = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("\r\n");

	return 1;
}

十三、测试结果

 

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
乘风的头像乘风管理团队
0
上一篇 2023年12月21日
下一篇 2023年12月21日

相关推荐