给定一棵二叉树，任务是使用Morris遍历进行逆序遍历。
null
在二叉树中 N 节点，有 n+1 浪费内存的空指针。因此，线程二叉树利用这些空指针来节省大量内存。 所以，在 线程二叉树 这些空指针将存储一些有用的信息。
1） 只在空的左指针中存储前置信息，称为左线程二叉树。 2） 仅将后续信息存储在空的右指针中，称为右线程二叉树。 3） 在空左指针中存储前置信息，在空右指针中存储后续信息，称为全线程二叉树或简单线程二叉树。
莫里斯穿越 可用于进行顺序遍历、反向顺序遍历、预顺序遍历，并消耗恒定的额外内存O（1）。
反向莫里斯穿越： 这只是莫里斯遍历的相反形式。在反向Morris遍历中，首先创建指向当前节点的顺序后续节点的链接，并使用这些链接打印数据，最后还原更改以恢复原始树，这将提供反向顺序遍历。
算法：
1) Initialize Current as root.2) While current is not NULL : 2.1) If current has no right child a) Visit the current node. b) Move to the left child of current. 2.2) Else, here we have 2 cases: a) Find the inorder successor of current node. Inorder successor is the left most node in the right subtree or right child itself. b) If the left child of the inorder successor is NULL: 1) Set current as the left child of its inorder successor. 2) Move current node to its right. c) Else, if the threaded link between the current node and it's inorder successor already exists : 1) Set left pointer of the inorder successor as NULL. 2) Visit Current node. 3) Move current to it's left child.
C++
// CPP code for reverse Morris Traversal #include<bits/stdc++.h> using namespace std; // Node structure struct Node { int data; Node *left, *right; }; // helper function to create a new node Node *newNode( int data){ Node *temp = new Node; temp->data = data; temp->right = temp->left = NULL; return temp; } // function for reverse inorder traversal void MorrisReverseInorder(Node *root) { if (!root) return ; // Auxiliary node pointers Node *curr, *successor; // initialize current as root curr = root; while (curr) { // case-1, if curr has no right child then // visit current and move to left child if (curr -> right == NULL) { cout << curr->data << " " ; curr = curr->left; } // case-2 else { // find the inorder successor of // current node i.e left most node in // right subtree or right child itself successor = curr->right; // finding left most in right subtree while (successor->left != NULL && successor->left != curr) successor = successor->left; // if the left of inorder successor is NULL if (successor->left == NULL) { // then connect left link to current node successor->left = curr; // move current to right child curr = curr->right; } // otherwise inorder successor's left is // not NULL and already left is linked // with current node else { successor->left = NULL; // visiting the current node cout << curr->data << " " ; // move current to its left child curr = curr->left; } } } } // Driver code int main() { /* Constructed binary tree is 1 / 2 3 / / 4 5 6 7 */ Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); //reverse inorder traversal. MorrisReverseInorder(root); return 0; } |
JAVA
// Java code for reverse Morris Traversal class GFG { // Node structure static class Node { int data; Node left, right; }; // helper function to create a new node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.right = temp.left = null ; return temp; } // function for reverse inorder traversal static void MorrisReverseInorder(Node root) { if (root == null ) return ; // Auxiliary node pointers Node curr, successor; // initialize current as root curr = root; while (curr != null ) { // case-1, if curr has no right child then // visit current and move to left child if (curr . right == null ) { System.out.print( curr.data + " " ); curr = curr.left; } // case-2 else { // find the inorder successor of // current node i.e left most node in // right subtree or right child itself successor = curr.right; // finding left most in right subtree while (successor.left != null && successor.left != curr) successor = successor.left; // if the left of inorder successor is null if (successor.left == null ) { // then connect left link to current node successor.left = curr; // move current to right child curr = curr.right; } // otherwise inorder successor's left is // not null and already left is linked // with current node else { successor.left = null ; // visiting the current node System.out.print( curr.data + " " ); // move current to its left child curr = curr.left; } } } } // Driver code public static void main(String args[]) { /* Constructed binary tree is 1 / 2 3 / / 4 5 6 7 */ Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.right.left = newNode( 6 ); root.right.right = newNode( 7 ); // reverse inorder traversal. MorrisReverseInorder(root); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 for reverse Morris Traversal # Utility function to create a new # tree node class newNode: def __init__( self ,data): self .data = data self .left = self .right = None # function for reverse inorder traversal def MorrisReverseInorder(root): if ( not root) : return # initialize current as root curr = root successor = 0 while (curr): # case-1, if curr has no right child then # visit current and move to left child if (curr.right = = None ) : print (curr.data, end = " " ) curr = curr.left # case-2 else : # find the inorder successor of # current node i.e left most node in # right subtree or right child itself successor = curr.right # finding left most in right subtree while (successor.left ! = None and successor.left ! = curr): successor = successor.left # if the left of inorder successor is None if (successor.left = = None ) : # then connect left link to current node successor.left = curr # move current to right child curr = curr.right # otherwise inorder successor's left is # not None and already left is linked # with current node else : successor.left = None # visiting the current node print (curr.data, end = " " ) # move current to its left child curr = curr.left # Driver code if __name__ = = "__main__" : """ Constructed binary tree is 1 / 2 3 / / 4 5 6 7 """ root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.right.left = newNode( 6 ) root.right.right = newNode( 7 ) #reverse inorder traversal. MorrisReverseInorder(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# code for reverse Morris Traversal using System; class GFG { // Node structure public class Node { public int data; public Node left, right; }; // helper function to create a new node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.right = temp.left = null ; return temp; } // function for reverse inorder traversal static void MorrisReverseInorder(Node root) { if (root == null ) return ; // Auxiliary node pointers Node curr, successor; // initialize current as root curr = root; while (curr != null ) { // case-1, if curr has no right child then // visit current and move to left child if (curr . right == null ) { Console.Write( curr.data + " " ); curr = curr.left; } // case-2 else { // find the inorder successor of // current node i.e left most node in // right subtree or right child itself successor = curr.right; // finding left most in right subtree while (successor.left != null && successor.left != curr) successor = successor.left; // if the left of inorder successor is null if (successor.left == null ) { // then connect left link to current node successor.left = curr; // move current to right child curr = curr.right; } // otherwise inorder successor's left is // not null and already left is linked // with current node else { successor.left = null ; // visiting the current node Console.Write( curr.data + " " ); // move current to its left child curr = curr.left; } } } } // Driver code public static void Main(String []args) { /* Constructed binary tree is 1 / 2 3 / / 4 5 6 7 */ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); // reverse inorder traversal. MorrisReverseInorder(root); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript code for reverse Morris Traversal // Node structure class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; // Helper function to create a new node function newNode(data) { var temp = new Node(); temp.data = data; temp.right = temp.left = null ; return temp; } // Function for reverse inorder traversal function MorrisReverseInorder(root) { if (root == null ) return ; // Auxiliary node pointers var curr, successor; // Initialize current as root curr = root; while (curr != null ) { // case-1, if curr has no right child then // visit current and move to left child if (curr . right == null ) { document.write( curr.data + " " ); curr = curr.left; } // case-2 else { // Find the inorder successor of // current node i.e left most node in // right subtree or right child itself successor = curr.right; // Finding left most in right subtree while (successor.left != null && successor.left != curr) successor = successor.left; // If the left of inorder successor is null if (successor.left == null ) { // Then connect left link to current node successor.left = curr; // Move current to right child curr = curr.right; } // Otherwise inorder successor's left is // not null and already left is linked // with current node else { successor.left = null ; // Visiting the current node document.write( curr.data + " " ); // Move current to its left child curr = curr.left; } } } } // Driver code /* Constructed binary tree is 1 / 2 3 / / 4 5 6 7 */ var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); // Reverse inorder traversal. MorrisReverseInorder(root); // This code is contributed by rrrtnx </script> |
输出：
7 3 6 1 5 2 4
时间复杂性： O（n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
