程序员的信仰

package com.jayxu;
 
import java.util.Iterator;
import java.util.Random;
import java.util.Stack;
 
/**
 *
 * @author ijay
 */
public class BinaryTree<T extends Comparable<T>> implements Iterable<T> {
    private static final char[] FIRST_CHAR = {'B', 'C', 'K', 'F', 'D', 'G'};
    private static final char[] FOLLOWING_CHAR = {'a', 'k', 'l', 'p', 'r', 't',
        'n', 'm', 's', 'e'};
    private static Random r = new Random(System.currentTimeMillis());
    private TreeNode root;
 
    public void addNode(T value) {
        root = addToNode(root, value);
    }
 
    private TreeNode addToNode(TreeNode node, T value) {
        if (node == null) {
            node = new TreeNode();
            node.value = value;
        } else if (value.compareTo(node.value) <= 0) {
            node.left = addToNode(node.left, value);
        } else {
            node.right = addToNode(node.right, value);
        }
 
        return node;
    }
 
    public Iterator<T> iterator() {
        return new PreOrderIterator();
    }
 
    private class TreeNode {
        TreeNode left;
        TreeNode right;
        T value;
    }
 
    private class PreOrderIterator implements Iterator<T> {
        private Stack<TreeNode> stack = new Stack<TreeNode>();
 
        private PreOrderIterator() {
            TreeNode current = root;
 
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
        }
 
        public boolean hasNext() {
            return !stack.isEmpty();
        }
 
        public T next() {
            TreeNode n = stack.pop();
 
            TreeNode current = n.right;
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
 
            return n.value;
        }
 
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
 
    public static void main(String[] args) {
        for (int i = 8; i < Integer.MAX_VALUE; i *= 2) {
            buildNTraverseTree(buildRawStrings(i), false);
        }
    }
 
    private static String[] buildRawStrings(int capacity) {
        String[] s = new String[capacity];
 
        s[0] = "Jay";
        s[1] = "Blader";
        s[2] = "Fred";
        s[3] = "Gavin";
        s[4] = "Alex";
 
        for (int i = 5; i < capacity; i++) {
            StringBuilder sb = new StringBuilder();
 
            sb.append(FIRST_CHAR[r.nextInt(FIRST_CHAR.length)]);
 
            int len = r.nextInt(10);
            for (int j = 0; j < len; j++) {
                sb.append(FOLLOWING_CHAR[r.nextInt(FOLLOWING_CHAR.length)]);
            }
 
            s[i] = sb.toString();
        }
 
        return s;
    }
 
    private static void buildNTraverseTree(String[] strings, boolean output) {
        System.out.print("Current capacity: " + strings.length + "\t");
        long start = System.currentTimeMillis();
 
        BinaryTree<String> tree = new BinaryTree<String>();
 
        for (String s : strings) {
            tree.addNode(s);
        }
 
        for (String s : tree) {
            if (output) {
                System.out.println(s);
            }
        }
 
        System.out.println("took " + (System.currentTimeMillis() - start)
                + " ms");
    }
}