排序树的创建及遍历

public class 树的创建与遍历 {
    static class Node{
        public int value;
        public Node left = null;
        public Node right = null;
        public Node(int value){
            this.value = value;
        }
    }
    public static Node root = null;


    //排序树的添加
    public void add(int value){
        Node val = new Node(value);
        if(root == null){
            root = val;
        }else{
          //当前节点，及执行一次add方法，就从头节点开始往下搜索
            Node current  =root;
         //添加时的一次搜索位置
            while (true) {
            //需要找到的节点
                Node pre = current;
            //排序树是左孩子小于该节点，右孩子大于该节点
                if (val.value < current.value) {
                    current = current.left;
                }else {
                    current = current.right;
                }
              //当找到要添加的位置时，判断需要添加该节点的左孩子还是右孩子位置
                if(current==null){   
                    if(val.value<pre.value){
                        pre.left = val;
                    }else {
                        pre.right = val;
                    }
                    break;  //找到添加后，这次添加就执行完毕
                }
            }
        }
    }


    //前序遍历
    public void showBefore(Node root){
        if(root==null){
            return;
        }
        System.out.print(root.value+" ");
        showBefore(root.left);
        showBefore(root.right);
    }


    //中序遍历
    public void showMiddle(Node root){
        if(root==null){
            return;
        }
        showMiddle(root.left);
        System.out.print(root.value+" ");
        showMiddle(root.right);
    }


    //后序遍历
    public void showAfter(Node root){
        if(root==null){
            return;
        }
        showAfter(root.left);
        showAfter(root.right);
        System.out.print(root.value+" ");
    }


    public static void main(String[] args) {
        树的创建与遍历 n = new 树的创建与遍历();
        n.add(10);
        n.add(20);
        n.add(30);
        n.add(40);
        n.add(35);
        System.out.println("前序遍历：");
        n.showBefore(root);
        System.out.println("中序遍历：");
        n.showMiddle(root);
        System.out.println("后序遍历：");
        n.showAfter(root);
    }

}

判断一个二叉树是否为平衡二叉树

根据先序遍历找到左右孩子为空的节点，该节点左右平衡。再往上找父节点，判断父节点的右孩子的节点是否平衡，若平衡，看该父节点的左右孩子是否平衡。

是不是很乱？嘻嘻，举个例子吧

以这块来说：

                                                 判断j节点平衡，h节点平衡，i节点平衡，f节点平衡，g节点平衡，c不平衡（因                                                                                 为Math.max(lh,rh)存有最大值，即c的左右孩子高度相差（5-2）>1）。

   可以Debug一下，看一下执行过程

/*
  输入一颗二叉树，判断该二叉树是否是平衡二叉树

  当左右孩子数量相差大于一时则不平衡
 */
public class 是否为平衡树 {
   static class Node{
        public int value;
        public Node left = null;
        public Node right = null;

        public Node(int value){
            this.value = value;
        }
    }
    public static Node root = null;

    //判断是否是平衡二叉树
  public static int heigth(Node node,int level,boolean[] x){
        if(node == null){
            if (level==1) {
                return level;
            }else {
                return level-1;
            }
        }
        int lh = heigth(node.left,level+1,x);
        if(x[0]==true){     //这个判断主要是不用再往下寻找，因为此时已经判断出来不是平衡二叉树
            return level-1;
        }
        int rh= heigth(node.right,level+1,x);
         if(x[0]==true){
          return level-1;
        }
        if(Math.abs(lh-rh)>1){   //大于一时不是平衡二叉树
            x[0]=true;  //此处已经存在不平衡树，所以后面直接可以不用再判断
        }
        return Math.max(lh,rh);
  }

    public static void main(String[] args) {
       //测试用例
      Node head = new Node(1);
      head.left = new Node(2);
      head.right = new Node(3);
      head.left.left = new Node(4);
      head.left.right = new Node(5);
      head.right.left = new Node(6);
      head.right.right = new Node(7);
      head.right.left.left = new Node(8);
      head.right.left.right = new Node(10);
      head.right.left.left.right = new Node(9);
      boolean[] x = {false};
      heigth(head,1,x);
      if(x[0]==true){
         System.out.println("不是平衡二叉树！");
      }else
        System.out.println("是平衡二叉树！");
   }
}