public class Node {
  int value;
  Node left;
  Node right;
  public Node(int value){
      this.value=value;
  }
  
  /**
   * 返回当前节点的高度
   * @return
   */
  public int hight(){
     return Math.max(left==null?0:left.hight(), 
             right==null?0:right.hight())+1;
  }
  
  /**
   * 设计思想，
   * 如果插入节点大于当前节点，插入右边
   * 否则插入左边。
   * @param node
   */
  public  void add(Node node) {
    if(node==null){
        return;
    }
    //如果传入节点比当前节点的值小
    if(this.value>node.value){
        if(this.left==null){
            this.left=node;
        }else{
            this.left.add(node);
        }
    }else{
        if(this.right==null){
            this.right=node;
        }else{
            this.right.add(node);
        }
    }
    if((
            (this.left==null?0:this.left.hight())-
            (this.right==null?0:this.right.hight()
                    ))>1){
        if(this.left!=null&&(
                (this.left.left==null?0:this.left.left.hight())<
                (this.left.right==null?0:this.left.right.hight()
                        ))){
            this.left.leftRotate();
        }
        //右旋转
        rightRotate();
    }else if((
            (this.left==null?0:this.left.hight())-
            (this.right==null?0:this.right.hight()
                    ))<-1){
        if(this.right!=null&&(
                (this.right.left==null?0:this.right.left.hight())>
                (this.right.right==null?0:this.right.right.hight()
                        ))){
            this.right.rightRotate();
        }
        //左旋转
        leftRotate();
    }
  }
  
  /**
   * 左旋转
   */
  private void leftRotate() {
      Node newNOde=new Node(value);
      newNOde.left=this.left;
      newNOde.right=this.right.left;
      value=this.right.value;
      this.left=newNOde;
      this.right=this.right.right;
 }

  /**
   * 右旋转
   */
  private void rightRotate() {
    Node newNOde=new Node(value);
    newNOde.right=this.right;
    newNOde.left=this.left.right;
    value=this.left.value;
    this.left=this.left.left;
    this.right=newNOde;
    
  }
}

package com.sun.test.Math.binarySortTree;

public class PinghengTree {
 public static void main(String[] args) {
     int[] a=new int[]{8,9,5,4,6,7};
     binarySortTree b=new binarySortTree();
    for(int i=0;i<a.length;i++){
        Node node=new Node(a[i]);
        b.add(node);
    }
    System.out.println(b.root.hight());
    System.out.println(b.root.value);
}
}