当前位置：首页 > news >正文

面试算法二叉树的遍历，方法递归，前序遍历: 中序遍历: 后序遍历: 层序遍历

news 来源：原创 2024/5/3 20:20:21

1.题目：

二叉树遍历
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
层序遍历:从上往下、从左往右

递归遍历:使用递归方法遍历

2.算法

1.递归算法

3.算法思想（这东西讲不清 bibi 看视频！！！）

1.前序遍历：首先在根开始向左遍历，到那个节点就打印数据，在递归左边节点，在递归右边节点，

2.中序遍历：首先在根开始遍历，遍历到最左边的时候才开始打印数据，因为是先打印左边啊！所以我们需要到最左边。然后递归右节点

3.后序遍历：首先我们先遍历到最左边，然后遍历最右边，最后打印数据。

4.层序遍历：首先我们，需要用到队列，的先进先出的特性来，实现。（开代码！！！不知道怎么说！！！）

4.仔细说明;

图中的先序遍历递归思想：

1.访问根结点，找到A；
2.访问结点A的左结点，找到B；
3.访问结点B的左结点，找到D；
4.由于结点D的左结点为空且又无右结点则D访问结束，返回结点B访问其右结点，找到E；
5.由于结点E无孩子，且结点B的左右孩子均访问，则返回结点A访问其右结点，找到C；
6.访问结点C的左结点，找到F；
7.由于F没有子结点，则返回访问结点C的右结点，访问失败，则返回A结点，由于结点A的左右结点8.均访问，则这个完全二叉树的先序遍历访问结束；

图中的中序遍历递归思想：

1.访问根结点，找到A；
2.找到A的左孩子，B；
3.找到B的左孩子，D；
4.由于结点D没有左孩子则访问D；
5.由于结点D也没有右孩子，则结点B的左子树遍历完成，访问B；
6.找到B的右孩子，E；
7.由于E无左子树，访问E；
8.由于E又无右子树，则A的左子树访问完成，访问A；
9.找到A的右孩子，C；
10.找到C的左孩子，F；
11.由于F没有左子树，则访问F；
12.由于F又没有右子树，则返回访问C；
13.由于C没有右子树，则返回A，中序遍历访问结束

图中的后序遍历递归思路：

1.从根结点A开始，遍历左孩子B；
2.遍历结点B的左孩子，找到D；
3.由于D没有左孩子，也没有右孩子，则访问D，并返回到结点B；
4.B的左孩子遍历完，开始遍历右孩子E，找到E；
5.由于E没有左右孩子，则访问E，并返回到结点B；
6.由于B结点左右孩子遍历完，则访问B，并返回到根结点A；
7.A的左孩子遍历完，开始遍历右孩子C，找到C；
8.遍历结点C的左孩子，找到F；
9.由于F没有左右孩子，则访问F，并返回到结点C；
10.C的左孩子遍历完，开始遍历右孩子，由于没有右孩子，则访问C，并返回到根结点A；
11.A的左右孩子均遍历完成，则访问A，后序遍历结束；

5.代码：

/*************************************************
作者：She001
时间:2022/9/31
题目：二叉树遍历
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
层序遍历:从上往下、从左往右

递归遍历:使用递归方法遍历


***************************************************/

#include<bits/stdc++.h>
using namespace std;


typedef struct student
{
	int a;
	struct student * left;
	struct student * right;
	int shendu;//树的深度 
}node;  //指针类型的 
/*//二叉树模型 
						
					a1
			a2              a3
		a4	  a5        a6     a7
		            a8
                       a9
*/
///

//递归的方法实现 
/*
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
层序遍历:从上往下、从左往右
*/


void fangfa_1(node *root)//递归方法的二叉树的前序遍历 
{
	if(root==NULL)
	{
		return ;	
	} 
	cout<<root->a<<"   ";
	fangfa_1(root->left);//一直往左边走， 
	fangfa_1(root->right);//左边走完了   往右边走  
} 

void fangfa_2(node * root)// 递归方法的二叉树的中序遍历 
{
	if(root ==NULL)
	{
		return ;	
	} 
	fangfa_2(root->left);//先走到最左边  
	cout<<root->a<<"   ";//打印数字 
	fangfa_2(root->right);//遍历右边的节点 
}


void fangfa_3(node *root)//递归方法的二叉树的后序遍历 
{
	if(root==NULL)
	{
		return ;	
	} 
	fangfa_3(root->left);//一直往左边走， 
	fangfa_3(root->right);//左边走完了   往右边走  
	cout<<root->a<<"   ";//打印数字 
	
} 

/*
思路:LeverOrderBiTree ()
1、判断当前队列是否为空deQueue ()
2、空:结束。不为空:取出头部第一个元素
3、将头结点的两个子节点入队   (字节点为 NULL  不入队列)




*/
//全局变量 队列
queue <node * >q;//建立队列 

void fangfa_4_1()//这里递归 
{
	if(q.empty())//判断队列是否为空
	{
		return;	
	}
	node * hh=q.front();//获得即将出队的数据
	cout<<hh->a<<"   ";//打印数据 
	q.pop();//出队； 
	if(hh->left!=NULL)
	{
		q.push(hh->left);
	} 
	if(hh->right!=NULL)
	{
		q.push(hh->right);
	} 
	fangfa_4_1();
}



void fangfa_4(node *root)//递归方法的二叉树的层序遍历 
{
	if(root==NULL)
	{
		cout<<"根是NULL 的"<<endl;
		return ;	
	} 
	//把根入队列 
	q.push(root);
	fangfa_4_1();
} 




int main()
{
	//数据初始化，建立树 
	struct student *a1 =new struct student; 
	struct student *a2 =new struct student; 
	struct student *a3 =new struct student; 
	struct student *a4 =new struct student; 
	struct student *a5 =new struct student; 
	struct student *a6 =new struct student; 
	struct student *a7 =new struct student; 
	struct student *a8 =new struct student; 
	struct student *a9 =new struct student; 
	//数值的赋值 
	a1->a=1; 
	a2->a=2; 
	a3->a=3; 
	a4->a=4; 
	a5->a=5; 
	a6->a=6; 
	a7->a=7; 
	a8->a=8; 
	a9->a=9; 
	//节点的连接 
	a1->left=a2;
	a1->right=a3;
	a2->left=a4;
	a2->right=a5;
	a3->left=a6;
	a3->right=a7;
	a6->left=a8;
	a8->right=a9;
	//节点为空的设置
	a4->left=NULL;
	a4->right=NULL;
	a5->left=NULL;
	a5->right=NULL;
	a8->left=NULL;
	a9->left=NULL;
	a9->right=NULL;
	a6->right=NULL;
	a7->left=NULL;
	a7->right=NULL;
	 
	 
	 
	//打印前序遍历
	cout<<"前序遍历：  "; 
	fangfa_1(a1); 
	cout<<endl; 
	
		//打印中序遍历
	cout<<"中序遍历：  "; 
	fangfa_2(a1); 
	cout<<endl; 
		
		//打印后序遍历 
	cout<<"后序遍历 ：  "; 
	fangfa_3(a1); 
	cout<<endl; 


		//打印层序遍历  
	cout<<"层序遍历  ：  "; 
	fangfa_4(a1); 
	cout<<endl; 
	
	
	//释放空间 
	delete a1;
	delete a2;
	delete a3;
	delete a4;
	delete a5;
	delete a6;
	delete a7;
	delete a8;
	delete a9;	

	return 	0;
}