博客

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

  • Post author:
  • Post category:其他


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

二叉树是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;
}

十三、测试结果


版权声明：本文为chenshengnanii原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。