package csdn;

import java.util.Date;
import java.util.Random;

public class TreeSort {

    public static void main(String[] args) {
        Integer[] ora = new Integer[20];
        Random r = new Random(new Date().getTime());
        for (int i = 0; i < 20; i++) {
            ora[i] = r.nextInt(1000);
            System.out.printf("%d->", ora[i]);
        }
        System.out.println();
        Tree<Integer> root = sortArray(ora);
        lastOrder(root);
        System.out.println();
    }

    public static <T extends Comparable> void lastOrder(Tree<T> root) {
        if (root != null) {
            if (root.left != null)
                lastOrder(root.left);
            System.out.printf("%d->", root.data);
            if (root.right != null)
                lastOrder(root.right);
        }
    }

    public static <T extends Comparable<T>> Tree<T> sortArray(T[] ora) {
        Tree<T> result = new Tree<T>();
        if (ora.length > 0)
            result.data = ora[0];
        T data;
        Tree<T> temp = result;
        for (int i = 1; i < ora.length; i++) {
            temp = result;
            data = ora[i];
            while (temp != null) {
                if (data.compareTo(temp.data) <= 0) {
                    if (temp.left != null) {
                        temp = temp.left;
                        continue;
                    } else {
                        temp.left = new Tree<T>();
                        temp.left.data = data;
                        break;
                    }
                } else {
                    if (temp.right != null) {
                        temp = temp.right;
                        continue;
                    } else {
                        temp.right = new Tree<T>();
                        temp.right.data = data;
                        break;
                    }
                }
            }
        }
        return result;
    }
}


class Tree<T extends Comparable> {

    public Tree<T> left  = null;
    public Tree<T> right = null;
    public T       data;
}