二叉树的递归与非递归遍历

对于二叉树的遍历，最简单的就是递归遍历，同时仿照递归算法执行过程中递归工作栈的变化可写出对应的非递归算法。

首先建立二叉树的结构类

 1 public class BiTree<T> {
 2     private T data;
 3     private BiTree<T> left;
 4     private BiTree<T> right;
 5     
 6     public BiTree(T data) {
 7         this.data = data;
 8         left = right = null;
 9     }
10     
11     public void setLeft(BiTree<T> left) {
12         this.left = left;
13     }
14     
15     public void setRight(BiTree<T> right) {
16         this.right = right;
17     }
18     
19     public void visit() {
20         System.out.print(data + " ");
21     }
22     
23     public BiTree<T> getLeft() {
24         return left;
25     }
26     
27     public BiTree<T> getRight() {
28         return right;
29     }
30 }

View Code

下面这个类提供了各种遍历的递归与非递归算法：

  1 import java.util.*;
  2 
  3 public class TreeUtil {
  4     public static <T> void preOrderTraverseRecursive(BiTree<T> tree) {
  5         if(tree == null) {
  6             return;
  7         }
  8         
  9         tree.visit();
 10         preOrderTraverseRecursive(tree.getLeft());
 11         preOrderTraverseRecursive(tree.getRight());
 12     }
 13     
 14     public static <T> void inOrderTraverseRecursive(BiTree<T> tree) {
 15         if(tree == null) {
 16             return;
 17         }
 18         
 19         inOrderTraverseRecursive(tree.getLeft());
 20         tree.visit();
 21         inOrderTraverseRecursive(tree.getRight());
 22     }
 23     
 24     public static <T> void postOrderTraverseRecursive(BiTree<T> tree) {
 25         if(tree == null) {
 26             return;
 27         }
 28         
 29         postOrderTraverseRecursive(tree.getLeft());
 30         postOrderTraverseRecursive(tree.getRight());
 31         tree.visit();
 32     }
 33     
 34         /*
 35          * 先序遍历非递归算法
 36          */
 37     public static <T> void preOrderTraverseNonRecursive(BiTree<T> tree) {
 38         if(tree == null) {
 39             return;
 40         }
 41         
 42         LinkedList<BiTree<T>> stack = new LinkedList<BiTree<T>>();
 43         BiTree<T> p = tree;
 44         
 45         while(p != null || !stack.isEmpty()) {
 46             if(p != null) {
 47                 p.visit();
 48                 stack.push(p.getRight());
 49                 p = p.getLeft();
 50             } else {
 51                 p = stack.pollFirst();
 52             }
 53         }
 54     }
 55     
 56         /*
 57          * 中序遍历非递归算法
 58          */
 59     public static <T> void inOrderTraverseNonRecursive(BiTree<T> tree) {
 60         if(tree == null) {
 61             return;
 62         }
 63         
 64         LinkedList<BiTree<T>> stack = new LinkedList<BiTree<T>>();
 65         BiTree<T> p = tree;
 66         
 67         while(p != null || !stack.isEmpty()) {
 68             if(p != null) {
 69                 stack.push(p);
 70                 p = p.getLeft();
 71             } else {
 72                 p = stack.pollFirst();
 73                 p.visit();
 74                 p = p.getRight();
 75             }
 76         }
 77     }
 78     
 79         /*
 80          * 后序遍历非递归算法
 81          */
 82     public static <T> void postOrderTraverseNonRecursive(BiTree<T> tree) {
 83         if(tree == null) {
 84             return;
 85         }
 86         
 87         LinkedList<BiTree<T>> stack = new LinkedList<BiTree<T>>();
 88         BiTree<T> p = tree;
 89         
 90         while(true) {
 91             if(p != null) {
 92                 stack.push(p);
 93                 stack.push(p.getRight());
 94                 p = p.getLeft();
 95             } else {
 96                 p = stack.pollFirst();
 97                 if(p == null) {
 98                     p = stack.pollFirst();
 99                     p.visit();
100                     if(stack.isEmpty()) return;
101                     p = stack.pollFirst();
102                 }
103                 stack.push(null);
104             }
105         }
106     }
107     
108     public static <T> BiTree<T> generateTreeFromArray(T[] array) {
109         if(array == null || array.length == 0) {
110             return null;
111         }
112         
113         int index = 0;
114         Queue<BiTree<T>> q = new LinkedList<BiTree<T>>();
115         BiTree<T> root = new BiTree<T>(array[index++]);
116         BiTree<T> current;
117         
118         q.offer(root);
119         while((current = q.poll()) != null && index < array.length) {
120             BiTree<T> left = new BiTree<T>(array[index++]);
121             q.offer(left);
122             current.setLeft(left);
123 
124             if(index < array.length) {
125                 BiTree<T> right = new BiTree<T>(array[index++]);
126                 q.offer(right);
127                 current.setRight(right);
128             }
129         }
130         
131         return root;
132     }
133 
134     public static void main(String[] args) {
135         BiTree<Integer> tree = generateTreeFromArray(new Integer[]{1,2,3,4,5,6,7,8,9,10});
136         preOrderTraverseRecursive(tree);
137         System.out.println();
138         preOrderTraverseNonRecursive(tree);
139         System.out.println();
140         inOrderTraverseRecursive(tree);
141         System.out.println();
142         inOrderTraverseNonRecursive(tree);
143         System.out.println();
144         postOrderTraverseRecursive(tree);
145         System.out.println();
146         postOrderTraverseNonRecursive(tree);
147         System.out.println();
148     }
149 }

View Code

遍历算法的基本操作是结点访问，对于含n个结点的二叉树，时间复杂度为O(n)。所需辅助空间为栈的最大容量，即树的深度，最坏情况下为n，所以空间复杂度也是O(n)。