实现树的中序遍历，无需递归且不使用栈！

本文概述

• C++
• Java
• Python 3
• C#

使用Morris遍历，我们无需使用栈和递归就可以遍历树。Morris遍历的思想是基于线程二叉树的。在这个遍历过程中，我们首先创建到Inorder继承者的链接，并使用这些链接打印数据，最后恢复更改以恢复原始树。

1. Initialize current as root 
2. While current is not NULL
   If the current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as the right child of the rightmost 
         node in current's left subtree
      b) Go to this left child, i.e., current = current->left

尽管通过遍历对树进行了修改, 但在完成后将其恢复为原始形状。不像基于栈的遍历, 此遍历不需要额外的空间。

C++

#include <stdio.h>
#include <stdlib.h>
  
/* A binary tree tNode has data, a pointer to left child
    and a pointer to right child */
struct tNode {
     int data;
     struct tNode* left;
     struct tNode* right;
};
  
/* Function to traverse the binary tree without recursion and 
    without stack */
void MorrisTraversal( struct tNode* root)
{
     struct tNode *current, *pre;
  
     if (root == NULL)
         return ;
  
     current = root;
     while (current != NULL) {
  
         if (current->left == NULL) {
             printf ( "%d " , current->data);
             current = current->right;
         }
         else {
  
             /* Find the inorder predecessor of current */
             pre = current->left;
             while (pre->right != NULL && pre->right != current)
                 pre = pre->right;
  
             /* Make current as the right child of its inorder 
                predecessor */
             if (pre->right == NULL) {
                 pre->right = current;
                 current = current->left;
             }
  
             /* Revert the changes made in the 'if' part to restore 
                the original tree i.e., fix the right child
                of predecessor */
             else {
                 pre->right = NULL;
                 printf ( "%d " , current->data);
                 current = current->right;
             } /* End of if condition pre->right == NULL */
         } /* End of if condition current->left == NULL*/
     } /* End of while */
}
  
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the
    given data and NULL left and right pointers. */
struct tNode* newtNode( int data)
{
     struct tNode* node = new tNode;
     node->data = data;
     node->left = NULL;
     node->right = NULL;
  
     return (node);
}
  
/* Driver program to test above functions*/
int main()
{
  
     /* Constructed binary tree is
             1
           /   \
          2     3
        /   \
       4     5
   */
     struct tNode* root = newtNode(1);
     root->left = newtNode(2);
     root->right = newtNode(3);
     root->left->left = newtNode(4);
     root->left->right = newtNode(5);
  
     MorrisTraversal(root);
  
     return 0;
}

Java

// Java program to print inorder traversal without recursion and stack
  
/* A binary tree tNode has data, a pointer to left child
    and a pointer to right child */
class tNode {
     int data;
     tNode left, right;
  
     tNode( int item)
     {
         data = item;
         left = right = null ;
     }
}
  
class BinaryTree {
     tNode root;
  
     /* Function to traverse a binary tree without recursion and 
        without stack */
     void MorrisTraversal(tNode root)
     {
         tNode current, pre;
  
         if (root == null )
             return ;
  
         current = root;
         while (current != null ) {
             if (current.left == null ) {
                 System.out.print(current.data + " " );
                 current = current.right;
             }
             else {
                 /* Find the inorder predecessor of current */
                 pre = current.left;
                 while (pre.right != null && pre.right != current)
                     pre = pre.right;
  
                 /* Make current as right child of its inorder predecessor */
                 if (pre.right == null ) {
                     pre.right = current;
                     current = current.left;
                 }
  
                 /* Revert the changes made in the 'if' part to restore the 
                     original tree i.e., fix the right child of predecessor*/
                 else {
                     pre.right = null ;
                     System.out.print(current.data + " " );
                     current = current.right;
                 } /* End of if condition pre->right == NULL */
  
             } /* End of if condition current->left == NULL*/
  
         } /* End of while */
     }
  
     public static void main(String args[])
     {
         /* Constructed binary tree is
                1
              /   \
             2      3
           /   \
          4     5
         */
         BinaryTree tree = new BinaryTree();
         tree.root = new tNode( 1 );
         tree.root.left = new tNode( 2 );
         tree.root.right = new tNode( 3 );
         tree.root.left.left = new tNode( 4 );
         tree.root.left.right = new tNode( 5 );
  
         tree.MorrisTraversal(tree.root);
     }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python 3

# Python program to do Morris inOrder Traversal:
# inorder traversal without recursion and without stack
  
class Node:
     """A binary tree node"""
     def __init__( self , data, left = None , right = None ):
         self .data = data
         self .left = left
         self .right = right
  
  
def morris_traversal(root):
     """Generator function for iterative inorder tree traversal"""
  
     current = root
      
     while current is not None :
          
         if current.left is None :
             yield current.data
             current = current.right
         else :
  
             # Find the inorder predecessor of current
             pre = current.left
             while pre.right is not None and pre.right is not current:
                 pre = pre.right
  
             if pre.right is None :
  
                 # Make current as right child of its inorder predecessor
                 pre.right = current
                 current = current.left        
  
             else :
                 # Revert the changes made in the 'if' part to restore the 
                 # original tree. i.e., fix the right child of predecessor
                 pre.right = None
                 yield current.data
                 current = current.right
              
# Driver program to test the above function
""" 
Constructed binary tree is
             1
           /   \
          2     3
        /   \
       4     5
"""
root = Node( 1 , right = Node( 3 ), left = Node( 2 , left = Node( 4 ), right = Node( 5 )
             )
        )
  
for v in morris_traversal(root):
     print (v, end = ' ' )
  
# This code is contributed by Naveen Aili
# updated by Elazar Gershuni

C#

// C# program to print inorder traversal
// without recursion and stack
using System;
  
/* A binary tree tNode has data, pointer to left child
     and a pointer to right child */
  
class BinaryTree 
{
     tNode root;
      
public class tNode 
{
     public int data;
     public tNode left, right;
  
     public tNode( int item)
     {
         data = item;
         left = right = null ;
     }
}
     /* Function to traverse binary tree without 
      recursion and without stack */
     void MorrisTraversal(tNode root)
     {
         tNode current, pre;
  
         if (root == null )
             return ;
  
         current = root;
         while (current != null )
         {
             if (current.left == null ) 
             {
                 Console.Write(current.data + " " );
                 current = current.right;
             }
             else 
             {
                 /* Find the inorder predecessor of current */
                 pre = current.left;
                 while (pre.right != null && pre.right != current)
                     pre = pre.right;
  
                 /* Make current as right child 
                 of its inorder predecessor */
                 if (pre.right == null ) 
                 {
                     pre.right = current;
                     current = current.left;
                 }
  
                 /* Revert the changes made in 
                 if part to restore the original 
                 tree i.e., fix the right child 
                 of predecssor*/
                 else
                 {
                     pre.right = null ;
                     Console.Write(current.data + " " );
                     current = current.right;
                 } /* End of if condition pre->right == NULL */
  
             } /* End of if condition current->left == NULL*/
  
         } /* End of while */
     }
  
     // Driver code
     public static void Main(String []args)
     {
         /* Constructed binary tree is
             1
             / \
             2     3
         / \
         4     5
         */
         BinaryTree tree = new BinaryTree();
         tree.root = new tNode(1);
         tree.root.left = new tNode(2);
         tree.root.right = new tNode(3);
         tree.root.left.left = new tNode(4);
         tree.root.left.right = new tNode(5);
  
         tree.MorrisTraversal(tree.root);
     }
}
  
// This code has been contributed 
// by Arnab Kundu

输出如下：

4 2 5 1 3

时间复杂度：O(n)，如果仔细观察, 会发现树的每个边缘最多被遍历两次。在最坏的情况下, 会创建和删除相同数量的额外边(与输入树一样)。

参考文献：

www.liacs.nl/~deutz/DS/september28.pdf

www.scss.tcd.ie/disciplines/software_systems/…/HughGibbonsSlides.pdf

如果你在上述代码/算法中发现任何错误, 或者想共享有关栈Morris有序树遍历的更多信息, 请写评论。