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

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

网站建设哪家好，找成都创新互联！专注于网页设计、网站建设、微信开发、微信平台小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了乌尔禾免费建站欢迎大家使用！

二、二叉树的遍历图解 先序遍历

中序遍历

后序遍历

层次遍历

三、代码部分 一、头文件 二、二叉树的结构 三、队列的结构 四、队列的初始化 五、判断队列是否为空 六、添加元素 七、删除元素 八、创建结点 九、创建二叉树 十、层次遍历 十一、主函数 十二、全部代码 十三、测试结果

一、头文件

#include#include#include#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#include#include#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;
}

十三、测试结果

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：二叉树的层次遍历（C语言）-创新互联
转载注明：http://lszwz.com/article/depcpo.html