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

本文概述

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 = http://www.srcmini.com/data; node-> left = NULL; node-> right = NULL; return (node); }/* Driver program to test above functions*/ int main() {/* Constructed binary tree is 1 / 23 / 45 */ 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 = http://www.srcmini.com/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 /\ 23 /\ 45 */ 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 stackclass Node: """A binary tree node""" def __init__( self , data, left = None , right = None ): self .data = http://www.srcmini.com/data self .left = left self .right = rightdef morris_traversal(root):"""Generator function for iterative inorder tree traversal"""current = rootwhile 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.rightif pre.right is None :# Make current as right child of its inorder predecessor pre.right = current current = current.leftelse : # 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 /\ 23 /\ 45 """ 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# 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 = http://www.srcmini.com/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 / \ 23 / \ 45 */ 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有序树遍历的更多信息, 请写评论。