1 public class Tree<T> {  2     private T data;  3     private Tree<T> left;  4     private Tree<T> right;  5   6     private Tree(T data) {  7         this.data =http://www.mamicode.com/ data;  8   9     } 10  11     public Tree(T[] datas) { 12         makeTree(datas, this); 13     } 14  15     public interface Visitor<T> { 16         void process(T data); 17     } 18  19     /** 20      * 递归中序遍历 21      *  22      * @param visitor 23      */ 24     public void recursionInOrder(Visitor<T> visitor) { 25         if (left != null)// 如果左子树存在，先访问左子树 26             left.recursionInOrder(visitor); 27         visitor.process(data);// 访问当前结点 28         if (right != null)// 如果右子树存在，访问右子树 29             right.recursionInOrder(visitor); 30     } 31  32     /** 33      * 递归先序遍历 34      *  35      * @param visitor 36      */ 37     public void recursionPreOrder(Visitor<T> visitor) { 38         visitor.process(data);// 访问当前结点 39         if (left != null)// 如果左子树存在，访问左子树 40             left.recursionPreOrder(visitor); 41         if (right != null)// 如果右子树存在，访问右子树 42             right.recursionPreOrder(visitor); 43     } 44  45     /** 46      * 递归后序遍历 47      *  48      * @param visitor 49      */ 50     public void recursionPostOrder(Visitor<T> visitor) { 51         if (left != null)// 如果左子树存在，先访问左子树 52             left.recursionInOrder(visitor); 53         if (right != null)// 如果右子树存在，访问右子树 54             right.recursionInOrder(visitor); 55         visitor.process(data);// 访问当前结点 56     } 57  58     /** 59      * 层次遍历 60      *  61      * @param visitor 62      */ 63     public void levelViste(Visitor<T> visitor) { 64         Queue<Tree<T>> queue = new LinkedList<Tree<T>>(); 65         queue.add(this); 66         while (!queue.isEmpty()) { 67             Tree<T> node = queue.poll(); 68             visitor.process(node.data); 69             if (node.left != null) 70                 queue.add(node.left); 71             if (node.right != null) 72                 queue.add(node.right); 73         } 74     } 75  76     /** 77      * 先序遍历 78      *  79      * @param visitor 80      */ 81     public void preOrderViste(Visitor<T> visitor) { 82         Stack<Tree<T>> stack = new Stack<Tree<T>>(); 83         Tree<T> node = this; 84         while (node != null || !stack.isEmpty()) { 85             if (node != null) {// 向左走到尽头 86                 visitor.process(node.data); 87                 stack.add(node); 88                 node = node.left; 89             } else { 90                 node = stack.pop(); 91                 node = node.right; 92             } 93         } 94     } 95  96     /** 97      * 中序遍历 98      *  99      * @param visitor100      */101     public void inOrderViste(Visitor<T> visitor) {102 103         Stack<Tree<T>> stack = new Stack<Tree<T>>();104         Tree<T> node = this;105         while (node != null || !stack.isEmpty()) {106             if (node != null) {// 向左走到尽头107                 stack.add(node);108                 node = node.left;109             } else {110                 node = stack.pop();111                 visitor.process(node.data);112                 node = node.right;113             }114         }115     }116 117     /**118      * 后续遍历119      * 120      * @param visitor121      */122     public void postOrderViste(Visitor<T> visitor) {123         Stack<Tree<T>> stack = new Stack<Tree<T>>();124         Tree<T> node = this, last = null;125         while (node != null || !stack.isEmpty()) {126             if (node != null) {// 向左走到尽头127                 stack.add(node);128                 node = node.left;129             } else {130                 node = stack.peek();131                 if (node.right != null && node.right != last) {// 有右孩子132                     node = node.right;// 向右走一步133                     stack.add(node);134                     node = node.left;// 向左走到尽头135                 } else {// 访问结点136                     node = stack.pop();137                     visitor.process(node.data);138                     last = node;139                     node = null;// 置为空，强制去探索右孩子140                 }141             }142         }143     }144 145     /**146      * 构造一个满二叉树147      * 148      * @param datas149      * @param root150      */151     public void makeTree(T[] datas, Tree<T> root) {152         List<Tree<T>> trees = new ArrayList<Tree<T>>(datas.length);153         root.data = http://www.mamicode.com/datas[0];154         trees.add(root);155         for (int i = 1; i < datas.length; i++) {156             trees.add(new Tree<T>(datas[i]));157         }158         int level = (int) (Math.log(datas.length) / Math.log(2));159         for (int i = 0; i <= level; i++) {160             int left = i * 2 + 1;161             if (left < datas.length)162                 trees.get(i).left = trees.get(left);163             int right = i * 2 + 2;164             if (right < datas.length)165                 trees.get(i).right = trees.get(right);166         }167     }168 169     private static Visitor<Integer> visitor = new Visitor<Integer>() {170         @Override171         public void process(Integer data) {172             System.out.print(data + " ");173         }174     };175 176     /**177      * 根据方法名测试访问178      * 179      * @param tree180      * @param method181      * @param visitor182      * @throws Exception183      */184     private static void test(Tree<?> tree, String method, Visitor<?> visitor)185             throws Exception {186         Class<?> c = (Class<?>) Class.forName("tree.Tree");187         Method func = c.getDeclaredMethod(method, Visitor.class);188         func.invoke(tree, visitor);189         System.out.println("(" + method + ")");190 191     }192 193     public static void main(String[] args) throws Exception {194         Integer[] datas = { 0, 1, 2, 3, 4, 5, 6, 7 };195         Tree<Integer> tree = new Tree<Integer>(datas);196         test(tree, "preOrderViste", visitor);197         test(tree, "inOrderViste", visitor);198         test(tree, "postOrderViste", visitor);199         test(tree, "inOrderViste", visitor);200         test(tree, "recursionInOrder", visitor);201         test(tree, "recursionPreOrder", visitor);202         test(tree, "recursionPostOrder", visitor);203         test(tree, "levelViste", visitor);204     }205 }