今天下午看见一条推

RT: @rtmeme: RT @foxzzz RT @junyu: 看到 @windbreaker 老师在Buzz说：今天是植树节，写一棵二叉树庆祝之 (via @yangfannet)

于是兴起，花了半个多小时写了棵自认为（从工程而非算法上）比较牛逼的排序二叉树

package com.jayxu;

import java.util.Iterator;
import java.util.Random;
import java.util.Stack;

/**
 *
 * @author ijay
 */
public class BinaryTree> implements Iterable {
    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 iterator() {
        return new PreOrderIterator();
    }

    private class TreeNode {
        TreeNode left;
        TreeNode right;
        T value;
    }

    private class PreOrderIterator implements Iterator {
        private Stack stack = new Stack();

        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 tree = new BinaryTree();

        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");
    }
}

该树特点：

  • 使用泛型
  • 实现Iterable接口从而能够使用增强for循环遍历
  • 实现非递归中序遍历
  • 生成随机数据测试