数据结构之二叉树的前中后序遍历以及层序遍历

一时失言乱红尘 2023-09-29 17:39 21阅读 0赞

## 学习目标：读完这篇博客搞定二叉树的前中后序以及层序遍历 ##

首先：你应该明白什么是二叉树，下面这幅图就是一个完全二叉树

![ff451a1bb517427889559720f801c288.png][]

其实所谓的二叉树就是一个节点有小于等于二个分支的树，可以没有分支，可以有1条分支，可以有两条分支，这便是二叉树

*  还有就是我们要理解二叉树的分治，以及递归，我们要把大事化小，一层一层来解决！

--------------------

## 学习内容：二叉树的前中后以及层序遍历的代码实现 ##

> 我们先来学习一下前序遍历吧，首先什么是前序遍历呢？其实二叉树有根，左子树以及右子树，而二叉树的前序遍历其实就是先遍历根节点在遍历左子树最后在遍历右子树，好讲了这么多都不如上代码来的实际！

> struct node  
> \{  
> datatype data;  
> struct node\* plch;  
> struct node\* prch;  
> \};
> 
> struct node\* create\_bree(void)  
> \{  
> struct node\* pa = malloc(sizeof(struct node));  
> struct node\* pb = malloc(sizeof(struct node));  
> struct node\* pc = malloc(sizeof(struct node));  
> struct node\* pd = malloc(sizeof(struct node));  
> struct node\* pe = malloc(sizeof(struct node));  
> struct node\* pf = malloc(sizeof(struct node));  
> struct node\* pg = malloc(sizeof(struct node));  
> struct node\* ph = malloc(sizeof(struct node));  
> struct node\* pi = malloc(sizeof(struct node));
> 
> pa->data = 'a';  
> pb->data = 'b';  
> pc->data = 'c';  
> pd->data = 'd';  
> pe->data = 'e';  
> pf->data = 'f';  
> pg->data = 'g';  
> ph->data = 'h';  
> pi->data = 'i';  
>   
> pa->plch = pb;  
> pa->prch = pc;
> 
> pb->plch = pd;  
> pb->prch = pe;  
>   
> pc->plch = NULL;  
> pc->prch = pf;
> 
> pd->plch = NULL;  
> pd->prch = NULL;  
>   
> pe->plch = pg;  
> pe->prch = ph;
> 
> pf->plch = pi;  
> pf->prch = NULL;
> 
> pg->plch = NULL;  
> pg->prch = NULL;  
>   
> ph->plch = NULL;  
> ph->prch = NULL;  
>   
> pi->plch = NULL;  
> pi->prch = NULL;
> 
> return pa;  
> \}  
> //先序遍历  
> void privot(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> if (proot->plch != NULL)  
> privot(proot->plch);  
> if (proot->prch != NULL)  
> privot(proot->prch);  
> \}  
> \}
> 
> int main()  
> \{  
> struct node\* pa = create\_bree();  
> privot(pa);  
> printf("\\n");
> 
> return 0;
> 
> \}

> 其实中序遍历和后序遍历的原理跟前序遍历的原理是差不多的，中序遍历的原理就是先遍历左子树在遍历根在遍历右子树，那么后序遍历的原理是什么呢？哈哈哈其实也是差不多的啦。就是先遍历左子树在遍历右子树，在遍历根噢，好啦直接上代码吧！

> void inorderprint(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot->plch != NULL)  
> inorderprint(proot->plch);  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> if (proot->prch != NULL)  
> inorderprint(proot->prch);  
> \}  
> \}  
> void houxuprint(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot->plch != NULL)  
> houxuprint(proot->plch);  
> if (proot->prch != NULL)  
> houxuprint(proot->prch);  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> \}  
> \}

##  ##

--------------------

> ## **最后的话，就来到最重点的时候了哦，就要来写我们的层序遍历了，层序遍历的算法我这里利用了链式队列来实现的，其实层序遍历就是一层一层遍历，从左到右遍历完一层就直接往下一层继续遍历。接下来就是放全部的代码啦！** ##

> \#define \_CRT\_SECURE\_NO\_WARNINGS 1  
> \#include <stdio.h>  
> \#include <stdbool.h>  
> \#include <stdlib.h>  
> \#include <assert.h>
> 
> typedef struct node\* QDataType;
> 
> typedef struct QueueNode  
> \{  
> struct QueueNode\* next;  
> QDataType data;  
> \}QNode;
> 
> typedef struct Queue  
> \{  
> QNode\* head;  
> QNode\* tail;  
> \}Queue;
> 
> void QueueInit(Queue\* pq)  
> \{  
> assert(pq);  
> pq->head = pq->tail = NULL;  
> \}  
> void QueueDestory(Queue\* pq)  
> \{  
> assert(pq);  
> QNode\* cur = pq->head;  
> while (cur)  
> \{  
> QNode\* next = cur->next;  
> free(cur);  
> cur = next;  
> \}  
> pq->head = pq->tail = NULL;  
> \}  
> //队尾入  
> void QueuePush(Queue\* pq, QDataType x)  
> \{  
> assert(pq);  
> QNode\* newnode = (QNode\*)malloc(sizeof(QNode));  
> if (newnode == NULL)  
> \{  
> printf("malloc fail\\n");  
> exit(-1);  
> \}  
> newnode->data = x;  
> newnode->next = NULL;  
> if (pq->tail == NULL)  
> \{  
> pq->head = pq->tail = newnode;  
> \}  
> else  
> \{  
> pq->tail->next = newnode;  
> pq->tail = newnode;  
> \}  
> \}  
> void QueuePop(Queue\* pq)  
> \{  
> assert(pq);  
> assert(pq->head);  
> if (pq->head->next == NULL)  
> \{  
> free(pq->head);  
> pq->head = pq->tail = NULL;  
> \}  
> else  
> \{  
> QNode\* next = pq->head->next;  
> free(pq->head);  
> pq->head = next;  
> \}
> 
> \}  
> QDataType QueueFront(Queue\* pq)  
> \{  
> assert(pq);  
> assert(pq->head);
> 
> return pq->head->data;  
> \}  
> QDataType QueueBack(Queue\* pq)  
> \{  
> assert(pq);  
> assert(pq->head);
> 
> return pq->tail->data;  
> \}  
> int QueueSize(Queue\* pq)  
> \{  
> assert(pq);  
> int size = 0;  
> QNode\* cur = pq->head;  
> while (cur)  
> \{  
> \++size;  
> cur = cur->next;  
> \}  
> return size;  
> \}  
> bool QueueEmpty(Queue\* pq)  
> \{  
> assert(pq);  
> return pq->head == NULL;  
> \}  
> typedef char datatype;
> 
> struct node  
> \{  
> datatype data;  
> struct node\* plch;  
> struct node\* prch;  
> \};
> 
> struct node\* create\_bree(void)  
> \{  
> struct node\* pa = malloc(sizeof(struct node));  
> struct node\* pb = malloc(sizeof(struct node));  
> struct node\* pc = malloc(sizeof(struct node));  
> struct node\* pd = malloc(sizeof(struct node));  
> struct node\* pe = malloc(sizeof(struct node));  
> struct node\* pf = malloc(sizeof(struct node));  
> struct node\* pg = malloc(sizeof(struct node));  
> struct node\* ph = malloc(sizeof(struct node));  
> struct node\* pi = malloc(sizeof(struct node));
> 
> pa->data = 'a';  
> pb->data = 'b';  
> pc->data = 'c';  
> pd->data = 'd';  
> pe->data = 'e';  
> pf->data = 'f';  
> pg->data = 'g';  
> ph->data = 'h';  
> pi->data = 'i';  
>   
> pa->plch = pb;  
> pa->prch = pc;
> 
> pb->plch = pd;  
> pb->prch = pe;  
>   
> pc->plch = NULL;  
> pc->prch = pf;
> 
> pd->plch = NULL;  
> pd->prch = NULL;  
>   
> pe->plch = pg;  
> pe->prch = ph;
> 
> pf->plch = pi;  
> pf->prch = NULL;
> 
> pg->plch = NULL;  
> pg->prch = NULL;  
>   
> ph->plch = NULL;  
> ph->prch = NULL;  
>   
> pi->plch = NULL;  
> pi->prch = NULL;
> 
> return pa;  
> \}  
> //先序遍历  
> void privot(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> if (proot->plch != NULL)  
> privot(proot->plch);  
> if (proot->prch != NULL)  
> privot(proot->prch);  
> \}  
>   
> \}  
> void inorderprint(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot->plch != NULL)  
> inorderprint(proot->plch);  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> if (proot->prch != NULL)  
> inorderprint(proot->prch);  
> \}  
> \}  
> void houxuprint(struct node\* proot)  
> \{  
> if (proot != NULL)  
> \{  
> if (proot->plch != NULL)  
> houxuprint(proot->plch);  
> if (proot->prch != NULL)  
> houxuprint(proot->prch);  
> if (proot != NULL)  
> printf("%c-->", proot->data);  
> \}  
> \}
> 
> void cengxubianli(struct node\* proot)  
> \{  
> if (proot == NULL)  
> \{  
> return;  
> \}  
> Queue pq;  
> QueueInit(&pq);  
> QueuePush(&pq, proot);  
> while (!QueueEmpty(&pq))  
> \{  
> struct node\* head = QueueFront(&pq);  
> QueuePop(&pq);  
> printf("%c ", head->data);  
> if (head->plch != NULL)  
> \{  
> QueuePush(&pq, head->plch);  
> \}  
> if (head->prch != NULL)  
> \{  
> QueuePush(&pq, head->prch);  
> \}  
> \}  
> printf("\\n");  
> \}  
> int main()  
> \{  
> struct node\* pa = create\_bree();  
> privot(pa);  
> printf("\\n");  
> inorderprint(pa);  
> printf("\\n");  
> houxuprint(pa);  
> printf("\\n");  
> cengxubianli(pa);  
> return 0;  
> \}  
>

好啦本次的代码就全部实现完啦，祝大家学习快乐！

[ff451a1bb517427889559720f801c288.png]: https://img-blog.csdnimg.cn/ff451a1bb517427889559720f801c288.png