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.