二叉树进阶之满二叉树和完全二叉树

转载请注明原文地址：http://www.cnblogs.com/ygj0930/p/6611702.html 

    一：满二叉树

    除了叶子结点无任何子节点外，每一层的结点都有两个子节点。也就是说：一棵满二叉树是一个完整的三角形 △  结构。

    满二叉树的性质：若满二叉树的层数为L，结点数为N，则： N=2^L-1。（结点数为 2的层数次方 减一）

   

    二：完全二叉树

    完全二叉树：1：一棵树，除了叶子节点那一层，上面的各层一定是满的。当最后一层也是满的，则树是完全二叉树也是满二叉树。

                     2：叶子结点那一层，结点严格按照“从左往右”插入。

    判断完全二叉树==按层遍历（用队实现即可，由于无需具体层信息，所以不需last和newlast来控制层）二叉树，

                            对每个出队结点：判据一：如果有右儿子无左儿子，则返回false；

                                                  判据二：如果有左儿子无右儿子，则队中剩下的一定全是叶结点，对之后每个出队的元素判断是否为叶。若有否的，则返回false。

                                                  如果遍历过程无返回false，则该树是完全二叉树， 返回true。

public class CheckCompletion {
    public boolean chk(TreeNode root) {
        if(root==null){
            return true;
        }
        
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);

        TreeNode curr=null;
        
        //判据二：当处理到一个出队元素有左儿子但无右儿子时，则此后出队的元素全是叶结点。开始对此后每个出队元素进行叶结点判断
        boolean leafbeg=false;
        while(!queue.isEmpty()){
            curr=queue.poll();
            //判据二
            if(leafbeg){
                if(!isLeaf(curr)){
                    return false;
                }
            }
            //判据一：有右儿子无左儿子，则直接返回false
            if(curr.left==null && curr.right!=null){
                return false;
            }
            
            //如果有左无右，则开启判据二
            if(curr.left!=null && curr.right==null){
                queue.offer(curr.left);                
                leafbeg=true;
            }
            //左右儿子全有，入队
            if(curr.left!=null && curr.right!=null){
                queue.offer(curr.left);
                queue.offer(curr.right);                
            }          
        }
        return true;
    }
    public boolean isLeaf(TreeNode node){
        if(node.left!=null||node.right!=null){
            return false;
        }
        return true;
    }
}