Java教程

前中后序遍历的递归与非递归算法,层序遍历

本文主要是介绍前中后序遍历的递归与非递归算法,层序遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言:
  • 思维导图
  • 建议
  • 递归的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 ;
	}
  1. 遍历顺序
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);

}

中序遍历

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

简介:左–根–右

image-20220225211321230

递归

思路

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

代码

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

后序遍历

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

简记:左-右-根

image-20220225211555017

递归

思路

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

代码

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

层序遍历

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

image-20220225213848032

image-20220225213940741

代码

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);
}
这篇关于前中后序遍历的递归与非递归算法,层序遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!