带你图解二叉树的多种递归遍历（建议收藏！！）

galaxy_robot 发布于2021-09-06 15:01 / 3303人阅读

摘要：但是这之间的递归过程是很复杂的。图解递归由于图片大小问题，建议用手机客户端查看，以下图解也是中序遍历中序遍历，又叫中根遍历。图解递归后序遍历后序遍历，又叫后根遍历。

文章目录

二叉树的构建
- 结点类型的定义
- 构建二叉树之间的关系
深度优先遍历
广度优先遍历
- 层序遍历
- - 代码实现

二叉树的构建

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

结点类型的定义

既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义

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);}

服务器托管专线服务二叉树的遍历非递归二叉树遍历二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119242.html

【数据结构初阶】新学期带你领跑二叉树，二叉树的迭代遍历，递归遍历详解，建议收藏

摘要：二叉树前言一二叉树的结构介绍二二叉树的遍历递归易前序遍历中序遍历后序遍历三二叉树的遍历迭代偏难利用队列进行迭代易非递归实现前中后序难前序遍历中序遍历后序遍历总结前言首先我们这里所讲述的二叉树是最为常见的，本章主要带大家 ...

CarlBenjamin 2021-09-10 10:50 评论0 收藏0
LeetCode通关：连刷三十九道二叉树，刷疯了！⭐四万字长文搞定二叉树，建议收藏！⭐

分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们收藏一下。二叉树基础二叉树是一种比较常见的数据结构，在开始刷二叉树...

honhon 2021-09-04 16:45 评论0 收藏0
PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
Java数据结构与算法——二叉树及操作(包括二叉树遍历)

摘要：本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度，可能是考试中的，也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作（三种遍历...

muddyway 2019-08-16 11:15 评论0 收藏0
【Leetcode】二叉树专题(仅需【7道题】就可以带你入门二叉树基本玩法)

摘要：文章目录一剑指二叉树的镜像剑指二叉树的镜像思路递归二剑指对称的二叉树剑指对称的二叉树思路递归三剑指二叉树的深度剑指二叉树的深度思路递归四剑指平衡二叉树剑指平衡二叉树思路递归五相同的 ...

lindroid 2021-11-18 10:02 评论0 收藏0