一、二叉树的概念以及结构
二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。
二、二叉树的遍历图解
先序遍历
中序遍历
后序遍历
层次遍历
三、代码部分
一、头文件
二、二叉树的结构
三、队列的结构
四、队列的初始化
五、判断队列是否为空
六、添加元素
七、删除元素
八、创建结点
九、创建二叉树
十、层次遍历
十一、主函数
十二、全部代码
十三、测试结果
一、头文件
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXSIZE 5文章来源地址https://www.toymoban.com/news/detail-730376.html
二、二叉树的结构
//二叉树的结构
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;
}十三、测试结果
文章来源：https://www.toymoban.com/news/detail-730376.html
到了这里，关于二叉树的层次遍历（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
