1. Title: Binary tree traversal
Preorder traversal: around the root
Inorder traversal: left root right
Postorder Traversal: Left and Right Roots
Layer order traversal: top to bottom, left to right

Algorithm: morris traversal

2. Algorithm:

morris algorithm:

3. Algorithm idea: (This thing is not clear, bibi watch the video!!!)

preorder traversal
Summary: 1. First encounter the left side of the node is NULL Print yourself, traverse your own right node
2. When the right node is empty, print the data node data and build a clue binary tree, continue to traverse its left node,
3. Encounter a clue binary tree, eliminate the clue binary tree, and traverse its own right node
 

In-order traversal
Summary: 1. When you first reach the leftmost point, you need to print the data
2. Print data when the thread is disconnected
3. The leftmost node of the node is NULL, print the data of the current node
 

post-order traversal
Summary: When disconnecting the clue binary tree, the linked list is reversed and the data is printed

4. Code:

/*************************************************
Author: She001
 Time:2022/9/31
 Title: Binary tree traversal
 Preorder traversal: around the root
 Inorder traversal: left root right
 Postorder Traversal: Left and Right Roots

Algorithm: morris traversal (threaded binary tree) 
***************************************************/

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


typedef struct student
{
	int a;
	struct student * left;
	struct student * right;
	int shendu;//tree depth 
}node;  //pointer type 
/*//Binary tree model 
						
					a1
			a2              a3
		a4	  a5        a6     a7
		            a8
                       a9
*/
///

//traversal method implementation 
/*
Preorder traversal: around the root
 Inorder traversal: left root right
 Postorder Traversal: Left and Right Roots
 Layer order traversal: top to bottom, left to right
*/

// Preorder traversal process of handwritten method 1   
/*
1.Start cur== a1 , define mostright=NULL , 
2.mostright = cur->left =a1->lift  = a2 ;||   mostright Enter the loop -> until mostright= a5 ,
3. Exit the while loop and enter the judgment The successful interpretation condition is mostright == NULL , so we build a clue binary tree ====|||a5 ->right =a1;||||====  
print data output data cur ->a = print a1->a ; cur=cur->left= a2; continue;
4.This time from a2 we start   
5. mostright = cur->lift =  a2->lift =a4;
6.Can't enter while loop because s4->right =NULL ;   
7. Enter the if judgment so =====||||a4 -> right = a2;|||||=====    
output data cur->a = output data a2-> a ; cur= cur->left =a4 continue;
8.This time from a4  
9.Start mostright= cur->left =a4 ->left =NULL
10. Enter the judgment of mostright ==NULL, the judgment is not established, so enter the inside of else and output the data cur ->a = a4->a Then we come out and finally have a cur =cur -> right = a4->right ; cur=a2 
11. cur=a2    mostright = a2->left = a4 ;  Enter while loop Exit loop because mostright ->right=cur ; delete clue binary tree cur = cur->right = a2->right= a5; 
12. This time from cur = a5 
13. mostright =cur ->left  =a5->left =NULL 
14.mostright =NULL   if Judgment, mostright =NULL so we enter the else space, so execute print data, cur ->a = a5->a, 
15.cur=cur->right  = a5->  right    = a1; 
16.mostright= cur->left =a2 ;  Enter the loop, exit the loop because mostright->right = a2-> right=a5 , mostright->right=a5->right =a1 , mostright ==cur This reason exits the loop
17.Enter judgment because mostright == cur so delete the connection of the clue binary tree!   cur = cur -> right = a1 -> a3;
18. mostright =cur->left  =a3->left  = a6   Enter the loop and judge mostright -> right =NULL ========|||||||| a6 ->right = a3;  
   print cur->a = a3->a ; cur=cur ->left = a3->left =a6; 
19. mostright = cur-> left = a6->left = a8 ;      mostright Enter the loop and stop at a9.  ======||||||||||||a9->right =a6;
	print cur ->a =a6 ->a ; cur= cur->left = a6->left = a8 ; 
20.mostright =cur ->left  =NULL   print a8->a cur=cur->right = a9; 
21. mostright= a9->left = NULL;  So stop, print cur->a = a9->a; cur =a9 ->right = a6 ;
21 mostright= cur-> left  =a8 ; a8->right = a9  a9 ->right =a6   mostright== cur  The loop stops so eliminate the clue binary tree, cur = cur->right = a6->right = a3; 
22.mostright = cur->left = a3->left=a6;   mostright->right ===cur End of loop so eliminate clue binary tree, cur = cur -> right = a7; 
23. mostright = a7->right =NULL  ;   Build a clue binary tree, a7->right = a7; , print a7 ; cur= cur->left = NULL ,
24.if   Judging cur == NULl to exit the outer loop! 
*/
/*
preorder traversal 
Summary: 1. First encounter the left side of the node is NULL and print itself, traverse its own right node  
 		2.When the right node is empty, print the data node data and build a clue binary tree, continue to traverse its left node, 
		 3.Encounter the clue binary tree, eliminate the clue binary tree, traverse its own right node 
*/
void fangfa_1(node * cur)//preorder traversal
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //Find the rightmost leaf node marker bit of the leftmost subtree
	while(cur !=NULL)
	{		
		mostright=cur->left;//The search starts, starting from the next left node of the current node, and starting to search, looking for the rightmost leaf node of the left subtree of the current node (if there is none, there is no)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//Always search, stop conditions, the first is that the right node of the current node is NULL, the second is that the current clue binary tree has been established, 
			{
				mostright=mostright->right;//go right 
			}
			if(mostright->right==NULL)//Find the rightmost node of the subtree of the cur node and build a clue binary tree 
			{
				mostright->right=cur;  //We build the clue binary tree to realize the subtree The rightmost node connects the current node 
				//Because this is a preorder traversal, we print when we get to the node
				cout<<cur->a<<"   ";
				cur=cur->left;//Find the clue binary tree of the node to the left of the current node
				continue; //end, loop again //prevent conflict with next step 
			}
			else//already contains the clue binary tree, we need to delete the node, 
			{
				mostright->right=NULL;//Delete the connection of the leaf node with the clue 
			} 		
		}
		else//When our mostright==NULL, we need to print the value // because it is the leftmost node of the binary tree at this time, print the value of the current node 
		{
			cout<<cur->a<<"   ";	//print value		
		}
		cur=cur->right; 
	} 
} 

/*
Inorder traversal 
Summary: 1. When you first reach the leftmost point, you need to print the data
       2.print data when disconnecting thread 
       3.The leftmost node of the node is NULL to print the data of the current node 
*/


void fangfa_2(node * cur)//Inorder traversal
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //Find the rightmost leaf node marker bit of the leftmost subtree
	while(cur !=NULL)
	{		
		mostright=cur->left;//The search starts, starting from the next left node of the current node, and starting to search, looking for the rightmost leaf node of the left subtree of the current node (if there is none, there is no)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//Always search, stop conditions, the first is that the right node of the current node is NULL, the second is that the current clue binary tree has been established, 
			{
				mostright=mostright->right;//go right 
			}
			if(mostright->right==NULL)//Find the rightmost node of the subtree of the cur node and build a clue binary tree 
			{
				mostright->right=cur;  //We build the clue binary tree to realize the subtree The rightmost node connects the current node 
			
				cur=cur->left;//Find the clue binary tree of the node to the left of the current node
				continue; //end, loop again //prevent conflict with next step 
			}
			else//already contains the clue binary tree, we need to delete the node, 
			{
				mostright->right=NULL;//Delete the connection of the leaf node with the clue 
			} 		
		}
		else//When our mostright==NULL, we need to print the value // because it is the leftmost node of the binary tree at this time, print the value of the current node 
		{
			
		}
		cout<<cur->a<<"   ";	//print value		
		cur=cur->right; 
	} 
} 

/*
post-order traversal
 Summary: When the clue binary tree is disconnected, the linked list is reversed and the data is printed 


*/

node* reverse(node* head)//linked list reversal 
{
	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)//print data, step, reverse linked list, print data, restore linked list, keep the integrity of binary tree
{
	node *hh = reverse(head);//first turn 
	node * ww=hh;//save the starting node 
	while(hh!=NULL)//print data 
	{
		cout<<hh->a<<"   ";
		hh=hh->right;
	}
	reverse(ww);	//reduction 
} 


void fangfa_3(node * cur)//Inorder traversal
{
	if(cur == NULL)
	{
		return ;
	} 
	node * mostright = NULL; //Find the rightmost leaf node marker bit of the leftmost subtree
	node * jj=cur;
	while(cur !=NULL)
	{		
		mostright=cur->left;//The search starts, starting from the next left node of the current node, and starting to search, looking for the rightmost leaf node of the left subtree of the current node (if there is none, there is no)
		if(mostright !=NULL)
		{
			while(mostright->right!=NULL && mostright->right!=cur)//Always search, stop conditions, the first is that the right node of the current node is NULL, the second is that the current clue binary tree has been established, 
			{
				mostright=mostright->right;//go right 
			}
			if(mostright->right==NULL)//Find the rightmost node of the subtree of the cur node and build a clue binary tree 
			{
				mostright->right=cur;  //We build the clue binary tree to realize the subtree The rightmost node connects the current node 
				
				cur=cur->left;//Find the clue binary tree of the node to the left of the current node
				continue; //end, loop again //prevent conflict with next step 
			}
			else//already contains the clue binary tree, we need to delete the node, 
			{
				
				mostright->right=NULL;//Delete the connection of the leaf node with the clue 
				printnode(cur->left);
			} 		
		}
		cur=cur->right; 
	} 
	printnode(jj);
} 







int main()
{
	//Data initialization, build tree 
	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; 
	//value assignment 
	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; 
	//node connection 
	a1->left=a2;
	a1->right=a3;
	a2->left=a4;
	a2->right=a5;
	a3->left=a6;
	a3->right=a7;
	a6->left=a8;
	a8->right=a9;
	//Node is empty settings
	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;
	
	
		//print preorder traversal
	cout<<"Preorder traversal:  "; 
	fangfa_1(a1); 
	cout<<endl; 
		//print in-order traversal
	cout<<"Inorder traversal:  "; 
	fangfa_2(a1); 
	cout<<endl; 
	
		
		//print postorder traversal 
	cout<<"Post-order traversal:  "; 
	fangfa_3(a1); 
	cout<<endl; 
	
	//free up space 
	delete a1;
	delete a2;
	delete a3;
	delete a4;
	delete a5;
	delete a6;
	delete a7;
	delete a8;
	delete a9;	

	return 	0;
} 

5. Interpretation of clue binary tree

The clue binary tree is a tree represented by a linked list, which is a tree composed of n + 1 idle pointers that are not used by the binary tree;
According to the three traversal methods of the binary tree, three different clue binary trees are formed;
The traversal of the binary tree can only be traversed sequentially from the root node, and after the clue binary tree is constructed, it can be traversed from any node in the binary tree, which is the biggest meaning of clue;
In fact, the application of the clue binary tree is very narrow, but the most important meaning of learning it is to understand its idea;
It is to make full use of the idle space, which should be the most important meaning;

Nature:

Traversing a binary tree is essentially a complex nonlinear structure convert to Linear structure , so that each node has a unique predecessor and successor (the first node has no predecessor, and the last node has no successor). For a node of a binary tree, it is convenient to find its left and right children, and its predecessors and successors can only be obtained during traversal. In order to easily find predecessors and successors, there are two methods. One is to add forward and backward pointers in the node structure, which increases storage overhead and is not desirable; the other is to use the empty chain pointer of the binary tree.

Advantage

(1) Using the clue binary tree to carry out Inorder traversal , it is not necessary to use stack The processing speed is faster than the traversal speed of the general binary tree, and the storage space is saved.

(2) Any node can directly find its predecessor and successor nodes. 

insufficient

(1) The insertion and deletion of nodes are troublesome and slow.

(2) Thread subtrees cannot be shared. 

Secret words:

In fact, no matter what kind of serialization, just remember the following three sentences:

• If the node has a left child: then Lchild points to its left child, otherwise it points to its predecessor in the traversal sequence.
• If the node has a right child: then Rchild still points to its left child, otherwise it points to the successor node of the traversal sequence.
• If there is no front or rear drive, it is NULL.