学步园

不使用递归遍历二叉树有几种方法：迭代，线索二叉树和Morris算法（通过临时转换二叉树变成一个类似链表的结构）。下面是迭代方法和递归的对比，后面单独列出Morris算法的实现。

迭代方法和递归的对比实现：

import java.util.Stack;<br /> /**<br /> *<br /> * Using recursive & iterative(ie. non-recursive) methods to traverse binary tree in<br /> * inorder, preorder and postorder<br /> *<br /> * @author ljs<br /> * 2011-05-25<br /> *<br /> *<br /> */<br /> public class BinTree {<br /> static class Node{<br /> int val;<br /> Node left;<br /> Node right;<br /> boolean visited;<br /> public Node(int val){<br /> this.val = val;<br /> }<br /> public String toString(){<br /> return String.valueOf(val);<br /> }<br /> }<br /> public static void recursiveInOrderTraverse(Node root){<br /> if(root == null)return;</p> <p> recursiveInOrderTraverse(root.left);<br /> System.out.format(" %d", root.val);<br /> recursiveInOrderTraverse(root.right);<br /> }</p> <p> @SuppressWarnings("unchecked")<br /> public static void iterativeInOrderTraverse(Node root){<br /> Stack stack = new Stack();<br /> Node node = root;<br /> while(true){<br /> if(node != null){<br /> stack.push(node);<br /> node = node.left;<br /> }else{<br /> if(!stack.isEmpty()){<br /> node = (Node)stack.pop();<br /> System.out.format(" %d", node.val); //visit<br /> node = node.right;<br /> }else{<br /> break;<br /> }<br /> }<br /> }<br /> }</p> <p> public static void recursivePreOrderTraverse(Node root){<br /> if(root == null)return;<br /> System.out.format(" %d", root.val);<br /> recursivePreOrderTraverse(root.left);<br /> recursivePreOrderTraverse(root.right);<br /> }<br /> @SuppressWarnings("unchecked")<br /> public static void iterativePreOrderTraverse1(Node root){<br /> if(root == null)return;</p> <p> Stack stack = new Stack();<br /> Node node = root;<br /> while(true){<br /> System.out.format(" %d", node.val); //visit<br /> if(node.right != null)<br /> stack.push(node.right);<br /> if(node.left != null)<br /> stack.push(node.left);</p> <p> if(!stack.isEmpty())<br /> node = (Node)stack.pop();<br /> else<br /> break;<br /> }<br /> }</p> <p> @SuppressWarnings("unchecked")<br /> public static void iterativePreOrderTraverse2(Node root){<br /> if(root == null)return;</p> <p> Stack stack = new Stack();<br /> Node node = root;<br /> while(true){<br /> if(node != null){<br /> System.out.format(" %d", node.val); //visit<br /> stack.push(node);<br /> node = node.left;<br /> }else{<br /> if(!stack.isEmpty()){<br /> node = (Node)stack.pop();<br /> node = node.right;<br /> }else{<br /> break;<br /> }<br /> }<br /> }<br /> }</p> <p> public static void recursivePostOrderTraverse(Node root){<br /> if(root == null)return;</p> <p> recursivePostOrderTraverse(root.left);<br /> recursivePostOrderTraverse(root.right);<br /> System.out.format(" %d", root.val);<br /> }<br /> @SuppressWarnings("unchecked")<br /> public static void iterativePostOrderTraverse(Node root){<br /> if(root == null)return;</p> <p> Stack stack = new Stack();<br /> Node node = root;<br /> Node lastNode = null;<br /> while(true){<br /> if(node != null){<br /> stack.push(node);<br /> node = node.left;<br /> }else{<br /> if(!stack.isEmpty()){<br /> node = (Node)stack.peek();<br /> node = node.right;</p> <p> if(node == null || node == lastNode){<br /> node = (Node)stack.pop();<br /> System.out.format(" %d", node.val); //visit </p> <p> lastNode = node;</p> <p> if(!stack.isEmpty()){<br /> node = (Node)stack.peek();<br /> node = node.right;<br /> if(node == lastNode){<br /> //set as null to let it execute the second branch in while<br /> node = null;<br /> }<br /> }else{<br /> break;<br /> }<br /> }<br /> }else{<br /> break;<br /> }<br /> }<br /> }<br /> }</p> <p> public static void main(String[] args){</p> <p> /*<br /> 14<br /> 10 25<br /> 2 12 20 31<br /> 13 19 21 29<br /> */<br /> Node n14 = new Node(14);<br /> Node n10 = new Node(10);<br /> Node n25 = new Node(25);<br /> Node n2 = new Node(2);<br /> Node n12 = new Node(12);<br /> Node n13 = new Node(13);<br /> Node n20 = new Node(20);<br /> Node n21 = new Node(21);<br /> Node n19 = new Node(19);<br /> Node n31 = new Node(31);<br /> Node n29 = new Node(29);</p> <p> n14.left = n10;<br /> n14.right = n25;<br /> n10.left = n2;<br /> n10.right = n12;<br /> n12.right = n13;<br /> n25.left = n20;<br /> n25.right = n31;<br /> n20.left = n19;<br /> n20.right = n21;<br /> n31.left = n29;</p> <p> System.out.format("preorder(recursive):%n");<br /> recursivePreOrderTraverse(n14);<br /> System.out.println();</p> <p> System.out.format("preorder(iterative 1):%n");<br /> iterativePreOrderTraverse1(n14);<br /> System.out.println();</p> <p> System.out.format("preorder(iterative 2):%n");<br /> iterativePreOrderTraverse2(n14);<br /> System.out.println();</p> <p> System.out.format("************************%n");</p> <p> System.out.format("postorder(recursive):%n");<br /> recursivePostOrderTraverse(n14);<br /> System.out.println();</p> <p> System.out.format("postorder(iterative):%n");<br /> iterativePostOrderTraverse(n14);<br /> System.out.println();</p> <p> System.out.format("************************%n");</p> <p> System.out.format("inorder(recursive):%n");<br /> recursiveInOrderTraverse(n14);<br /> System.out.println();</p> <p> System.out.format("inorder(iterative):%n");<br /> iterativeInOrderTraverse(n14);<br /> System.out.println();</p> <p> }<br /> }<br />

测试输出：

preorder(recursive):
 14 10 2 12 13 25 20 19 21 31 29
preorder(iterative 1):
 14 10 2 12 13 25 20 19 21 31 29
preorder(iterative 2):
 14 10 2 12 13 25 20 19 21 31 29
************************
postorder(recursive):
 2 13 12 10 19 21 20 29 31 25 14
postorder(iterative):
 2 13 12 10 19 21 20 29 31 25 14
************************
inorder(recursive):
 2 10 12 13 14 19 20 21 25 29 31
inorder(iterative):
 2 10 12 13 14 19 20 21 25 29 31

Morris算法的实现：

public static void morrisInOrder(Node node){</p> <p> Node p = node;<br /> Node tmp = null;<br /> while(p != null){<br /> if(p.left == null){<br /> System.out.format(" %d", p.val);<br /> p = p.right;<br /> }else{<br /> //the left side(including the fake case)</p> <p> tmp = p.left;<br /> //find the p's predecessor<br /> while(tmp.right != null<br /> && tmp.right != p) {<br /> tmp = tmp.right;<br /> }<br /> if(tmp.right == null){ //transform<br /> //the tmp is the leaf<br /> //establish a fake right node<br /> tmp.right = p;<br /> //next root<br /> p = p.left;<br /> }else{ //restore the fake link: tmp.right == p<br /> System.out.format(" %d", p.val);<br /> tmp.right = null;<br /> p = p.right;<br /> }<br /> }<br /> }<br /> }<br />