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

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

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

十三、测试结果