数据结构|带你图解二叉树的多种递归遍历（建议收藏！！） c语言|算法|数据结构

文章目录

二叉树的构建
- 结点类型的定义
- 构建二叉树之间的关系
深度优先遍历
- 前序遍历
- - 代码实现
  - 图解递归（由于图片大小问题，建议用手机客户端查看，以下图解也是）
- 中序遍历
- - 代码实现
  - 图解递归
- 后序遍历
- - 代码实现
  - 图解递归
广度优先遍历
- 层序遍历
- - 代码实现

二叉树的构建

为了实现二叉树的遍历，我们要先构建一个二叉树，这里就先简单构建一个。

结点类型的定义

【数据结构|带你图解二叉树的多种递归遍历（建议收藏！！）】既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义

typedef char BTDataType; typedef struct BinaryNode { BTDataType x; struct BinaryNode* left; struct BinaryNode* right; }BT;

构建二叉树之间的关系

BT* BuyNode(BTDataType x) { BT* new = (BT*)malloc(sizeof(BT)); if (new == NULL) {printf("malloc failed\n"); exit(-1); } new->x = x; new->left = NULL; new->right = NULL; return new; }void BinaryCreat() { BT* n1 = BuyNode('A'); BT* n2 = BuyNode('B'); BT* n3 = BuyNode('C'); BT* n4 = BuyNode('D'); BT* n5 = BuyNode('E'); BT* n6 = BuyNode('F'); n1->left = n2; n1->right = n3; n2->left = n4; n3->left = n5; n3->right = n6; }

构建完之后的二叉树是这个样子的：

文章图片

深度优先遍历

二叉树的深度优先遍历有以下三种

前序遍历

前序遍历，又叫先根遍历。
遍历顺序：根 -> 左子树 -> 右子树

代码实现

void BinaryPrev(BT* n1) { if (n1==NULL) {printf("NULL "); return ; } printf("%c ", n1->x); BinaryPrev(n1->left); BinaryPrev(n1->right); }

很多小伙伴可能会觉得：哇！这么少的代码就可以解决了吗？对，就是这么几行，这也就是递归遍历的强大之处。但是这之间的递归过程是很复杂的。

图解递归（由于图片大小问题，建议用手机客户端查看，以下图解也是）

文章图片

中序遍历

中序遍历，又叫中根遍历。
遍历顺序：左子树 -> 根 -> 右子树

代码实现

void MiddleOrder(BT* n1) { if (n1 == NULL) {printf("NULL "); return; } MiddleOrder(n1->left); printf("%c ", n1->x); MiddleOrder(n1->right); }

这个也是同样的简单，只要按着它的顺序写就行了，但其中的过程很复杂。

图解递归

文章图片

后序遍历

后序遍历，又叫后根遍历。
遍历顺序：左子树 -> 右子树 -> 根

代码实现

void AfterOrder(BT* n1) { if (n1 == NULL) {printf("NULL "); return; } AfterOrder(n1->left); AfterOrder(n1->right); printf("%c ", n1->x); }

这个同样也是只要按着顺序写就可以了，递归起来很复杂。

图解递归

文章图片

广度优先遍历层序遍历

层序遍历，自上而下，从左往右逐层访问树的结点的过程就是层序遍历。

文章图片

思路（借助一个队列）：
1.先把根入队列，然后开始从队头出数据。
2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
3.重复进行步骤2，直到队列为空为止。

代码实现

在实现过程中要用到队列，具体队列的实现这儿就不说了，博主之前的博客中有相关的文章。

void BinaryLevelOrder(BT* n1) { Queue q; QueueInit(&q); if (n1!=NULL) {QueuePush(&q, n1); } while (!QueueEmpty(&q)) {BT* front = QueueTop(&q); QueuePop(&q); printf("%c ", front->x); // 不把NULL打印出来 //if (front->left!=NULL) //{// QueuePush(&q, front->left); //} //if (front->right != NULL) //{// QueuePush(&q, front->right); //} if (front->left != NULL) {QueuePush(&q, front->left); } else {printf("NULL "); } if (front->right != NULL) {QueuePush(&q, front->right); } else {printf("NULL "); } } QueueDestory(&q); }