文章目录

• 前言：
• 思维导图
• 建议
• 递归的3要素
• 二叉树的遍历
• 前序遍历
• • 递归
  • • 思路
    • 完整代码
  • 非递归
  • • 思路
    • 代码
• 中序遍历
• • 递归
  • • 思路
    • 代码
  • 非递归
  • • 思路
    • 代码
• 后序遍历
• • 递归
  • • 思路
    • 代码
  • 非递归
  • • 思路
    • 代码
• 层序遍历
• • 代码

前言：

• 本文介绍，遍历的递归与非递归算法,其中后序遍历的非递归是最难的。
• 博主收录的问题:New Young
• 转载请标明出处：New Young

思维导图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vOghesek-1645797380622)(%E9%81%8D%E5%8E%86.assets/202202252155405.png)]

建议

1. 二叉树是一种递归结构!!!!!!!!!,这一点一定要时刻牢记。
2. 递归利用 分而自治的思想 ，对于解决二叉树问题，很方便
3. 递归我们一般建议先判断假的情况，这会很大层度方便解决问题。
4. 在使用递归时，如果不能一下完成所有代码，可以先完成大致的部分，之后慢慢补齐细节问题。

递归的3要素

• 递归函数返回值的使用问题
• 递归函数的参数设置问题
• 递归的结束条件的判断问题。

二叉树的遍历

遍历的意思就是：打印一个二叉树中的每个结点的值，但是因为存在左右子树，二叉树的遍历有4种：前序遍历，中序遍历，后序遍历，层序遍历

PS:

1. 对与空结点，默认打印NULL,方便查看。
2. 遍历只能遍历玩当前的树，才能遍历其它的上一层树，或者兄弟层树。

前序遍历

要求在遍历二叉树的左右子树前，先打印根结点的值，在遍历左子树，当左子树遍历完，再遍历右子树。

简记：根-左-右

递归

思路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EEBW1k5Y-1645797380638)(%E9%81%8D%E5%8E%86.assets/image-20220225162701635-16457776228533.png)]

依据三要素：

1. 前序遍历函数不需要返回值，因此void

2. 参数，只需要一个指针就行了，因此

void PreOrder(BTNode* root);// 二叉树前序遍历---递归法

3.结束条件：

if(root==NULL)
	{
		printf("NULL ");
		return ;
	}

4. 遍历顺序

printf("%c ", root->data);
 PreOrder(root->left);
 PreOrder(root->right)

完整代码

//前序遍历是根在左右孩子前，先访问二叉树根结点。
void PreOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL ");
		return ;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

非递归

思路

我们知道函数栈帧是发生在栈区的，而这个栈区的特点(先进后出，先用低地址后用高地址)和数据结构中的栈是相同的，因此这里我们可以通过数据结构的栈来模拟函数栈帧时的栈区。

• 首先因为栈的特点–先进后出，因此左子树必须先被访问，因此我们先将右子树的地址存放的数组栈中，再将左子树存到数组栈中。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dPQCyN7D-1645797380639)(%E9%81%8D%E5%8E%86.assets/202202252053310.png)]

代码

void PreOrderNoR(BTNode* root)// 二叉树前序遍历---非递归法
{
	assert(root);
	stack st;
	StackInit(&st);
	//我们需要根结点来进入右子树，因此要存根结点
	//同时一旦左子树访问完后，再进入右子树时需要根结点，后面就不需要了。因此pop
	SDateType p = root;
	while (1)
	{
		if (p != NULL)
		{
			printf("%c->", p->data);
			StackPush(&st, p);
			p = p->left;
		}
		else
		{
			printf("NULL->");
			break;
		}
	}

	while (!StackEmpty(&st)||p)//空树或者栈空结束
	{
		/
		//p为空说明，根和左子树遍历完毕。
		
		if (!StackEmpty(&st))
		{
			p = StackTop(&st);
			StackPop(&st);
			p = p->right;
			while (1)
			{
				if (p != NULL)
				{
					printf("%c->", p->data);
					StackPush(&st, p);
					p = p->left;
				}
				else
				{
					printf("NULL->");
					break;
				}
			}
		}
	}
	printf("\n");

	StackDestroy(&st);

}

中序遍历

再访问根结点前，先访问左子树，当左子树为空后，再访问根结点，然后访问右子树。

简介：左–根–右

递归

思路

同前序遍历差不多，需要将左子树递归完，再访问根结点。

代码

void InOrder(BTNode* root)// 二叉树中序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

非递归

思路

同样使用栈模拟栈区。

但是数组栈中要先存放左子树的地址，当存入空树后，就可以访问根结点，然后遍历右子树，重复这个过程。

代码

void InOrderNoR(BTNode* root)// 二叉树中序遍历---递归法
{
	assert(root);
	stack st;
	StackInit(&st);
	//我们需要根结点来进入右子树，因此要存根
	SDateType p = root;
	//遍历到左子树最低端.
	while (1)
	{
		if (p != NULL)
		{
			StackPush(&st, p);
			p = p->left;
		}
		else
		{
			printf("NULL->");
			break;
		}
	}
	while (!StackEmpty(&st) || p)//空树或者栈空结束
	{
		 
		if (!StackEmpty(&st))
		{
			SDateType  tmp= StackTop(&st);
			printf("%c->", tmp->data);
			StackPop(&st);
			p = tmp->right;
			//根结点已经遍历玩比，后续的遍历就不需要它了。
			//无论右子树是否为空，即使回来也不需要根结点。
			//遍历到左子树最低端.
			while (1)
			{
				if (p != NULL)
				{
					StackPush(&st, p);
					p = p->left;
				}
				else
				{
					printf("NULL->");
					break;
				}
			}
		}
	}
	printf("\n"); 
	StackDestroy(&st);
}

后序遍历

在访问根结点前，要把 左，右子树访问完，才能访问根结点。

简记：左-右-根

递归

思路

和前序相似，只是需要先将左右访问结束，再访问根结点

代码

void PostOrder(BTNode* root)// 二叉树后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

非递归

思路

1.只有当左右子树访问完后，才能访问根结点。
因此要有一个pVisist指针来记录已访问的左或右子树。当pVisit=p->right||p- >right==NULL时，访问根结点。
2.我们访问存在的右子树时，仍把它看作一棵二叉树，因此仍需要压栈与出栈，
3.这里我打印NULL来帮助更好理解，

代码

void PostOrderNoR(BTNode* root)// 二叉树后序遍历---非递归法
{
	//思路：1.只有当左右子树访问完后，才能访问根结点。
	//      因此要有一个pVisist指针来记录已访问的左或右子树。当pVisit=p->right||p->right==NULL时，访问根结点。
	//      2.我们访问存在的右子树时，仍把它看作一棵二叉树，因此仍需要压栈与出栈，
	//      3.这里我打印NULL来帮助更好理解，
	assert(root);
	assert(root);
	stack st;
	StackInit(&st);
	SDateType p = root;
	SDateType pVisit = NULL;//标记左右子树的
	//简化版--只是将Top赋值给p了，但是要注意当右子树不为空，一定要直接进行左子树入栈。因为p的值并不是空。
	while (1)//先将左子树压栈，当左子树为空后，开始访问右子树。
	{
		if (p == NULL)
		{
			printf("NULL->");
			break;
		}
		else
		{
			StackPush(&st, p);
			p = p->left;
		}
	}
	while (!StackEmpty(&st) || p)//空树或者栈空结束
	{

		if (!StackEmpty(&st))
		{
			 p = StackTop(&st);
			//只有当右子树为空或者右子树已访问才访问根结点,才能删除根结点.
			if (p->right == NULL || p->right == pVisit)
			{
				if (p->right == NULL)
				{
					printf("NULL->");

				}
				StackPop(&st);
				printf("%c->", p->data);
				pVisit = p;
				//这一部代表该子树已访问，但是不确实是左子树还是右子树，因此需要 p->right == pVisit
			}
			else
			{
				p = p->right;//下次循环将是右子树的遍历。
				while (1)
				{
					if (p == NULL)
					{
						printf("NULL->");
						break;
					}
					else
					{
						StackPush(&st, p);
						p = p->left;
					}
				}
			}
		}
	}
	printf("\n");


	StackDestroy(&st);
}

层序遍历

• 层序遍历与前中后不同。它要求必须将树一层的结点遍历完，再遍历下一层。
• 层序遍历利用队列来实现层序遍历。
• 注意因为队列的特点（先进先出），需要左子树要先入队列。

代码

void LevelOrder(BTNode* root)// 层序遍历
{
	if (root == NULL)
	{
		return;
	
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueTop(&q);
		printf("%c ", tmp->data);
		QueuePop(&q);
		if (tmp->left != NULL)
		{
			QueuePush(&q, tmp->left);
		
		}
		if (tmp->right != NULL)
		{
			QueuePush(&q, tmp->right);
		}

	}
	QueueDestroy(&q);
}