完全二叉树的判断

什么是完全二叉树？

 一棵深度为k的有n个结点的 二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树（百度）

判断是不是完全二叉树条件有两点

第一点：任意结点，有右无左,就不是完全二叉树

第二点：在第一点不违规的情况下，如果遇到了第一个左右子树不全的结点，后序皆是叶结点

1.  
   private static boolean isBST(Node head){
2.  
   if(head == null){
3.  
   return true;
4.  
   }
5.  
   //和先遍历一样，用一个队列存储结点
6.  
   Queue<Node> queue = new LinkedList<>();
7.  
   Node left = null;
8.  
   Node right = null;
9.  
   //记录遇到了第一个左右不满的结点
10.  
    boolean leaf = false;
11.  
    queue.add(head);
12.  
    while(!queue.isEmpty()){
13.  
    head = queue.poll();
14.  
    left = head.left;
15.  
    right = head.right;
16.  
    //如果leaf为ture那么就已经遇到了第一个左右不满的结点，
17.  
    // 往后遍历过程中只有当左右孩子都为空时才是完全二叉树
18.  
    if((leaf && (left != null || right != null)) ||
19.  
    //有右孩子无左孩子
20.  
    (left == null && right != null)){
21.  
    return false;
22.  
    }
23.  
    if(left != null){
24.  
    queue.add(left);
25.  
    }
26.  
    if(right != null){
27.  
    queue.add(right);
28.  
    }
29.  
    //当左右孩子中有一个为空，leaf就标记
30.  
    if(left == null || right == null){
31.  
    leaf = true;
32.  
    }
33.  
    }
34.  
    return true;
35.  
    }

这篇好文章是转载于：学新通技术网