（转）二叉树分类

转自：http://blog.csdn.net/brillianteagle/article/details/39118937

一、完全二叉树的判断

参考：http://blog.csdn.net/lilypp/article/details/6158699/

【分析】根节点开始进行层次遍历，节点入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。

[java] view plaincopy
 
  1. /*使用LinkedList实现队列，入队使用queue.offer(),出队使用queue.poll()*/  
  2.        Queue<BinaryTreeNode<T>> queue=new LinkedList<>();  
  3.         boolean flag=true;  
  4.        queue.offer(root);  
  5.         while (!queue.isEmpty()) {  
  6.            BinaryTreeNode<T> tempNode=queue.poll();  
  7.             if (tempNode.getLeftChild()!=null&&flag){  
  8.                queue.offer(tempNode.getLeftChild());  
  9.            }else if (tempNode.getLeftChild()!=null) {  
  10.                 return false;  
  11.            }else {  
  12.                 flag=false;  
  13.            }  
  14.              
  15.             if (tempNode.getRightChild()!=null&&flag){  
  16.                queue.offer(tempNode.getRightChild());  
  17.            }else if (tempNode.getRightChild()!=null) {  
  18.                 return false;  
  19.            }else {  
  20.                 flag=false;  
  21.            }  
  22.              
  23.            }  
  24.         /*如果遍历完成仍然没有返回false，表明是完全二叉树*/  
  25.         return true;  
  26.        }  



二、平衡二叉树的判断

【分析-1】从root开始往下递归判断节点的左右子树的深度差（动态规划问题，但不容易加入备忘机制，所以比较低效） 。子树的深度被重复计算，所以比较低效。

/*递归判断左右子树的深度，如果深度差的绝对值大于1表明非平衡树*/

   

[java] view plaincopy
 
  1. public  int isBalancedTree(BinaryTreeNode<T> node) {  
  2.        if (node==null) {  
  3.            return 1;  
  4.       }  
  5.        int leftDepth=getTreeDeep(node.getLeftChild());  
  6.        int rightDepth=getTreeDeep(node.getRightChild());  
  7.        int diff=leftDepth-rightDepth;  
  8.        if (diff<-1||diff>1) {  
  9.            return 0;  
  10.       }else {  
  11.            if (isBalancedTree(node.getLeftChild())==1&&isBalancedTree(node.getRightChild())==1){  
  12.                return 1;  
  13.           }else {  
  14.                return 0;  
  15.           }  
  16.             
  17.       }  
  18.         
  19.    }  
  20.    /* 获得树的高度，递归过程 */  
  21.    private int getTreeDeep(BinaryTreeNode<T> root) {  
  22.        if (root == null) {  
  23.            return 0;  
  24.       }  
  25.        if (root.getLeftChild() == null && root.getRightChild() == null) {  
  26.            return 1;  
  27.       }  
  28.   
  29.        return 1 + Math.max(getTreeDeep(root.getLeftChild()),  
  30.               getTreeDeep(root.getRightChild()));  
  31.    }  

【分析-2】利用动态规划的方法从底向上计算每个子数的深度。从顶向下递归传递一个Depth 对象，探底之后就从底向上开始计算，本质上是后续遍历。这里要注意，Depth depth需要传址调用，所以不能用int或Interger,而要新定义一个类。

[java] view plaincopy
 
  1. /*isBalancedTree(node.getLeftChild(),leftDepth)&&isBalancedTree(node.getRightChild(),rightDepth)表明先左边探底，然后上移一个节点计算右子数，是后续遍历过程*/  
  2.         public boolean isBalancedTree(BinaryTreeNode<T> node,Depth depth){  
  3.       if (node==null) {  
  4.            depth=new Depth(0);  
  5.          return true;  
  6.          }  
  7.         Depth leftDepth=new Depth(0),rightDepth=new Depth(0);  
  8.         if (isBalancedTree(node.getLeftChild(),leftDepth)&&isBalancedTree(node.getRightChild(),rightDepth)){  
  9.             int diff=leftDepth.getDepth()-rightDepth.getDepth();  
  10.             if (diff<=1&&diff>=-1) {  
  11.                depth.setDepth(1 + Math.max(leftDepth.getDepth(),rightDepth.getDepth()));  
  12.                System.out.println(depth.getDepth());  
  13.                 return true;  
  14.            }  
  15.        }  
  16.         return false;  
  17.    }  
  18.     public boolean isBalancedTree(){  
  19.         return isBalancedTree(root, new Depth(0));  
  20.    }  
  21.     class Depth{  
  22.         int depth;  
  23.         public Depth(int depth) {  
  24.             // TODO 自动生成的构造函数存根  
  25.             this.depth=depth;  
  26.        }  
  27.    
  28.         public int getDepth() {  
  29.             return depth;  
  30.        }  
  31.    
  32.         public void setDepth(int depth) {  
  33.             this.depth = depth;  
  34.        }  
  35.          
  36.    }  



三、二叉搜索树（BST）的判断

参考：http://www.2cto.com/kf/201310/250996.html

【分析】BST的中序遍历是递增数列，所以可以利用中序遍历来进行判断。这里也是递归调用，需要传址调用，所以不能用int或Interger来定义pre。

先设计一个类：

 

[java] view plaincopy
 
  1. class Pre{  
  2.     int pre;  
  3.    
  4.     public int getPre() {  
  5.         return pre;  
  6.     }  
  7.    
  8.     public void setPre(int pre) {  
  9.         this.pre = pre;  
  10.     }  
  11.      
  12. }  



函数体：

 

[java] view plaincopy
 
    1. public staticbooleanisBST(BinarySearchTreesNode<String> root) {  
    2.         Prepre=new Pre();  
    3.         pre.setPre(Integer.MIN_VALUE);  
    4.         return isBSTOrder(root, pre);  
    5.          
    6.     }  
    7.     public static booleanisBSTOrder(BinarySearchTreesNode<String> root,Pre pre) {  
    8.         if (root==null) {  
    9.             return true;  
    10.         }  
    11.         if (isBSTOrder(root.getLeftChild(), pre)) {  
    12.             if (root.getKey()>pre.getPre()) {  
    13.                 pre.setPre(root.getKey());  
    14.                 return isBSTOrder(root.getRightChild(), pre);  
    15.             }else {  
    16.                 return false;  
    17.             }  
    18.         }  
    19.          
    20.             return false;  
    21.          
    22.     }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/sunshisonghit/p/4548298.html