面试算法 二叉树的遍历，方法 ：线索二叉树 ( morris ) ，前序遍历: 中序遍历: 后序遍历

1.题目：二叉树遍历
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
层序遍历:从上往下、从左往右

 算法： morris遍历

2.算法：

morris算法：

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

前序遍历 
总结： 1.首先遇到节点左边是 NULL  打印自己 ，遍历自己的右节点  
     2.遇到右节点为空 ，打印数据 节点数据    还有 就是建立线索二叉树，继续遍历自己的左节点， 
         3.遇到线索二叉树，消除线索二叉树 ,遍历自己的 右节点 
 

中序遍历 
总结： 1.首先到达最左边的时候 需要打印数据
       2.断开线索连接的时候 打印数据 
       3.节点的最左边为 NULL  打印当前节点的数据 
 

后序遍历
总结： 断开线索二叉树的时候，链表反转，打印数据 

4.代码：

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

算法 ： morris遍历(线索二叉树) 
***************************************************/

#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
*/
///

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

// 手写方法1 的 前序遍历  过程   
/*
1.开始  cur== a1  ,定义了 mostright=NULL   ， 
2.mostright = cur->left =a1->lift  = a2 ;||   mostright 进入循环 ->  一直到  mostright= a5 ,
3. 退出 while 循环 进入判断  判读条件成功的为  mostright == NULL   ,所以我们建立 线索二叉树     ====|||a5 ->right =a1;||||====  
打印数据  输出数据    cur ->a =  打印 a1->a   ; cur=cur->left= a2; continue;
4.这次从 a2 开始  我们开始   
5. mostright = cur->lift =  a2->lift =a4;
6.不能进入while 循环 ，因为 s4->right =NULL ;   
7. 进入if  判断  所以      =====||||a4 -> right = a2;|||||=====    
输出数据 cur->a   =  输出数据 a2-> a  ;     cur= cur->left  =a4   continue;
8.这次从 a4 开始  
9.开始  mostright= cur->left =a4 ->left =NULL
10. 进入 mostright ==NULL  的判断  判断不成立 所以进入 else 的里面 输出数据   cur ->a   =  a4->a    然后我们的出来最后有一个  cur =cur -> right =  a4->right ; cur=a2 
11. cur=a2    mostright = a2->left = a4 ;  进入 while  循环   退出循环，， 因为 mostright ->right=cur  ;  删除 线索二叉树 cur  = cur->right = a2->right= a5; 
12. 这时候 从 cur =  a5 开始 
13. mostright =cur ->left  =a5->left =NULL 
14.mostright =NULL   if 判断  ，  mostright =NULL  所以我们进入 else  空间 ，所以执行  打印数据，cur ->a  =  a5->a  , 
15.cur=cur->right  = a5->  right    = a1; 
16.mostright= cur->left =a2 ;  进入循环 ， 退出循环因为  mostright->right = a2-> right=a5 , mostright->right=a5->right =a1  ,  mostright ==cur 这个原因退出循环
17.进入判断  因为 mostright == cur 所以 删除 线索二叉树的连接！  cur = cur -> right  = a1 -> a3;
18. mostright =cur->left  =a3->left  = a6   进入 循环出来   判断   mostright -> right =NULL       ========||||||||  a6  ->right  = a3;  
   打印 cur-> a  = a3->a ;   cur=cur ->left = a3->left =a6; 
19. mostright = cur-> left = a6->left = a8 ;      mostright进入循环 ，直到  a9 的时候停止。 ======||||||||||||a9->right =a6;
	打印cur ->a  =a6 ->a    ;  cur= cur->left = a6->left = a8 ; 
20.mostright =cur ->left  =NULL   打印 a8->a   cur=cur->right  = a9; 
21. mostright= a9->left = NULL;  所以  停止，打印 cur-> a = a9->a;  cur =a9 ->right  = a6 ;
21 mostright= cur-> left  =a8 ; a8->right = a9  a9 ->right =a6   mostright== cur  循环停止  所以消除线索二叉树  ， cur = cur->right = a6-> right = a3; 
22.mostright = cur->left = a3->left=a6;   mostright->right ===cur 循环结束   所以消除线索二叉树 ， cur = cur -> right = a7; 
23. mostright = a7->right =NULL  ;   建立线索二叉树， a7->right = a7;  , 打印 a7  ;  cur= cur->left = NULL  ,
24.if   判断   cur  == NULl  退出外部的大循环！ 
*/
/*
前序遍历 
总结： 1.首先遇到节点左边是 NULL  打印自己 ，遍历自己的右节点  
 		2.遇到右节点为空 ，打印数据 节点数据    还有 就是建立线索二叉树，继续遍历自己的左节点， 
		 3.遇到线索二叉树，消除线索二叉树 ,遍历自己的 右节点 
*/
void fangfa_1(node * cur)//前序遍历
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //寻找最左边子树的 最靠右的叶子节点   标记位
	while(cur !=NULL)
	{		
		mostright=cur->left;//寻找开始，从当前节点的下一个左边节点 ，开始寻找，寻找当前节点左子树的最靠右的叶子节点   (假如没有就 没有)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//一直找，停止的条件，第一个是当前节点的右节点为 NULL  ， 第二个是 当前线索二叉树已经建立， 
			{
				mostright=mostright->right;//往右走 
			}
			if(mostright->right==NULL)//找到了 cur 节点的子树的最右边节点 ,建立线索二叉树 
			{
				mostright->right=cur;  //我们建立线索二叉树  实现子树 最右边的节点 连接 当前的节点 
				//因为 这个是 前序的遍历，所以我们到了 节点 就打印
				cout<<cur->a<<"   ";
				cur=cur->left;//寻找当前节点的左边节点的线索二叉树
				continue; //结束，再次循环 //防止与下一步冲突 
			}
			else//已经含有线索二叉树，我们需要删除节点， 
			{
				mostright->right=NULL;//删除含有线索的叶子节点 的连接 
			} 		
		}
		else//当我们的  mostright==NULL  的时候我们需要打印数值 // 因为此时是二叉树的最左边的节点 ，打印当前的节点的值 
		{
			cout<<cur->a<<"   ";	//打印数值		
		}
		cur=cur->right; 
	} 
} 

/*
中序遍历 
总结： 1.首先到达最左边的时候 需要打印数据
       2.断开线索连接的时候 打印数据 
       3.节点的最左边为 NULL  打印当前节点的数据 
*/


void fangfa_2(node * cur)//中序遍历
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //寻找最左边子树的 最靠右的叶子节点   标记位
	while(cur !=NULL)
	{		
		mostright=cur->left;//寻找开始，从当前节点的下一个左边节点 ，开始寻找，寻找当前节点左子树的最靠右的叶子节点   (假如没有就 没有)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//一直找，停止的条件，第一个是当前节点的右节点为 NULL  ， 第二个是 当前线索二叉树已经建立， 
			{
				mostright=mostright->right;//往右走 
			}
			if(mostright->right==NULL)//找到了 cur 节点的子树的最右边节点 ,建立线索二叉树 
			{
				mostright->right=cur;  //我们建立线索二叉树  实现子树 最右边的节点 连接 当前的节点 
			
				cur=cur->left;//寻找当前节点的左边节点的线索二叉树
				continue; //结束，再次循环 //防止与下一步冲突 
			}
			else//已经含有线索二叉树，我们需要删除节点， 
			{
				mostright->right=NULL;//删除含有线索的叶子节点 的连接 
			} 		
		}
		else//当我们的  mostright==NULL  的时候我们需要打印数值 // 因为此时是二叉树的最左边的节点 ，打印当前的节点的值 
		{
			
		}
		cout<<cur->a<<"   ";	//打印数值		
		cur=cur->right; 
	} 
} 

/*
后序遍历
总结： 断开线索二叉树的时候，链表反转，打印数据 


*/

node* reverse(node* head)//链表反转 
{
	node* prev =NULL;
	node* curr;
	node* next;
	curr=head;
	while(curr!=NULL)
	{
		next=curr->right;
		curr->right=prev;
		prev=curr;
		curr=next;
	}
	return prev;
	
}


void printnode(node *head)//打印数据  ，步骤，链表反转，打印数据，还原链表，保持二叉树的完整性
{
	node *hh = reverse(head);//第一反过来 
	node * ww=hh;//保存开头的节点 
	while(hh!=NULL)//打印数据 
	{
		cout<<hh->a<<"   ";
		hh=hh->right;
	}
	reverse(ww);	//还原 
} 


void fangfa_3(node * cur)//中序遍历
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //寻找最左边子树的 最靠右的叶子节点   标记位
	node * jj=cur;
	while(cur !=NULL)
	{		
		mostright=cur->left;//寻找开始，从当前节点的下一个左边节点 ，开始寻找，寻找当前节点左子树的最靠右的叶子节点   (假如没有就 没有)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//一直找，停止的条件，第一个是当前节点的右节点为 NULL  ， 第二个是 当前线索二叉树已经建立， 
			{
				mostright=mostright->right;//往右走 
			}
			if(mostright->right==NULL)//找到了 cur 节点的子树的最右边节点 ,建立线索二叉树 
			{
				mostright->right=cur;  //我们建立线索二叉树  实现子树 最右边的节点 连接 当前的节点 
				
				cur=cur->left;//寻找当前节点的左边节点的线索二叉树
				continue; //结束，再次循环 //防止与下一步冲突 
			}
			else//已经含有线索二叉树，我们需要删除节点， 
			{
				
				mostright->right=NULL;//删除含有线索的叶子节点 的连接 
				printnode(cur->left);
			} 		
		}
		cur=cur->right; 
	} 
	printnode(jj);
} 







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; 
	
	//释放空间 
	delete a1;
	delete a2;
	delete a3;
	delete a4;
	delete a5;
	delete a6;
	delete a7;
	delete a8;
	delete a9;	

	return 	0;
} 

 5.线索二叉树的解释

线索二叉树是链表表示的树，它是利用了二叉树未被使用的 n + 1个闲置的指针构成的树；
根据二叉树的三种遍历方式构成了三种不同的线索二叉树；
二叉树的遍历只能从根结点开始依次遍历，而构建了线索二叉树后，就可以从二叉树中任何一个结点进行遍历，这就是线索化最大的意义了；
实际上线索二叉树的应用面是很窄的，但是学习它最重要的意义还是理解它的这种思想；
就是将闲置的空间充分利用起来，这应该是最重要的意义了；

本质：

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

(2)任意一个结点都能直接找到它的前驱和后继结点。