/**
 * 無(wú)論排序的對(duì)象是什么，都要實(shí)現(xiàn)Comparable接口
 *
 * @param <T>
 */
public class BinaryNode<T extends Comparable<T>> {
  private static int index = 0; // 排序下標(biāo)
  private static int len = 0; // 最大數(shù)組長(zhǎng)度
  private T t; // 根節(jié)點(diǎn)
  private BinaryNode<T> left; // 左側(cè)葉子節(jié)點(diǎn)
  private BinaryNode<T> right; // 右側(cè)葉子節(jié)點(diǎn)
  public BinaryNode(T t) {
    len++;
    this.t = t;
  }
  /**
   * 往一顆書中插入值，在本質(zhì)上都通過(guò)根節(jié)點(diǎn)一層層的判斷。
   * 如果根節(jié)點(diǎn)不存在則新建節(jié)點(diǎn)
   * 如果根節(jié)點(diǎn)存在則判斷應(yīng)該在左側(cè)還是在右側(cè)插入，通常是左小右大
   * 
   * @param t
   */
  public void insert(T t) {
    if (this.t.compareTo(t) > 0) {
      if (this.left == null) {
        BinaryNode<T> node = new BinaryNode<T>(t);
        this.left = node;
      } else {
        this.left.insert(t);
      }
    } else {
      if (this.right == null) {
        BinaryNode<T> node = new BinaryNode<T>(t);
        this.right = node;
      } else {
        this.right.insert(t);
      }
    }
  }
  /**
   * 調(diào)用私有方法
   * 
   * @return
   */
  public Comparable<?>[] order() {
    Comparable<?>[] os = new Comparable[len];
    order(this, os);
    return os;
  }
  /**
   * 利用中序遍歷查找整顆樹
   * 
   * @param bn
   * @param os
   */
  private void order(BinaryNode<T> bn, Comparable<?>[] os) {
    if (bn.left == null) {
      os[index++] = bn.t;
    } else {
      order(bn.left, os);
      os[index++] = bn.t;
    }
    if (bn.right == null) {
      return;
    } else {
      order(bn.right, os);
    }
  }
}