二叉树的递归,非递归遍历(java)

  1 import java.util.Stack;
  2 import java.util.HashMap;
  3 
  4 public class BinTree {
  5     private char date;
  6     private BinTree lchild;
  7     private BinTree rchild;
  8 
  9     public BinTree(char c) {
 10         date = c;
 11     }
 12 
 13     // 先序遍历递归
 14     public static void preOrder(BinTree t) {
 15         if (t == null) {
 16             return;
 17         }
 18         System.out.print(t.date);
 19         preOrder(t.lchild);
 20         preOrder(t.rchild);
 21     }
 22 
 23     // 中序遍历递归
 24     public static void InOrder(BinTree t) {
 25         if (t == null) {
 26             return;
 27         }
 28         InOrder(t.lchild);
 29         System.out.print(t.date);
 30         InOrder(t.rchild);
 31     }
 32 
 33     // 后序遍历递归
 34     public static void PostOrder(BinTree t) {
 35         if (t == null) {
 36             return;
 37         }
 38         PostOrder(t.lchild);
 39         PostOrder(t.rchild);
 40         System.out.print(t.date);
 41     }
 42 
 43     // 先序遍历非递归
 44     public static void preOrder2(BinTree t) {
 45         Stack<BinTree> s = new Stack<BinTree>();
 46         while (t != null || !s.empty()) {
 47             while (t != null) {
 48                 System.out.print(t.date);
 49                 s.push(t);
 50                 t = t.lchild;
 51             }
 52             if (!s.empty()) {
 53                 t = s.pop();
 54                 t = t.rchild;
 55             }
 56         }
 57     }
 58 
 59     // 中序遍历非递归
 60     public static void InOrder2(BinTree t) {
 61         Stack<BinTree> s = new Stack<BinTree>();
 62         while (t != null || !s.empty()) {
 63             while (t != null) {
 64                 s.push(t);
 65                 t = t.lchild;
 66             }
 67             if (!s.empty()) {
 68                 t = s.pop();
 69                 System.out.print(t.date);
 70                 t = t.rchild;
 71             }
 72         }
 73     }
 74 
 75     // 后序遍历非递归
 76     public static void PostOrder2(BinTree t) {
 77         Stack<BinTree> s = new Stack<BinTree>();
 78         Stack<Integer> s2 = new Stack<Integer>();
 79         Integer i = new Integer(1);
 80         while (t != null || !s.empty()) {
 81             while (t != null) {
 82                 s.push(t);
 83                 s2.push(new Integer(0));
 84                 t = t.lchild;
 85             }
 86             while (!s.empty() && s2.peek().equals(i)) {
 87                 s2.pop();
 88                 System.out.print(s.pop().date);
 89             }
 90 
 91             if (!s.empty()) {
 92                 s2.pop();
 93                 s2.push(new Integer(1));
 94                 t = s.peek();
 95                 t = t.rchild;
 96             }
 97         }
 98     }
 99 
100     public static void main(String[] args) {
101         BinTree b1 = new BinTree('a');
102         BinTree b2 = new BinTree('b');
103         BinTree b3 = new BinTree('c');
104         BinTree b4 = new BinTree('d');
105         BinTree b5 = new BinTree('e');
106 
107         /**
108          *      a 
109          *     / /
110          *    b   c
111          *   / /
112          *  d   e
113          */
114         b1.lchild = b2;
115         b1.rchild = b3;
116         b2.lchild = b4;
117         b2.rchild = b5;
118 
119         BinTree.preOrder(b1);
120         System.out.println();
121         BinTree.preOrder2(b1);
122         System.out.println();
123         BinTree.InOrder(b1);
124         System.out.println();
125         BinTree.InOrder2(b1);
126         System.out.println();
127         BinTree.PostOrder(b1);
128         System.out.println();
129         BinTree.PostOrder2(b1);
130     }
131 }