完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
实现判断思想:
若想判断该树是不是完全二叉树,需要看该树的结点是否满足完全二叉树规则造成的结点特性
- 按层遍历该树每个结点,若该结点有右孩子结点,那么该结点必然要有左孩子结点
- 若该结点不是两个孩子结点都有(有左孩子没右孩子,或者左右孩子均为空),那么后面遇到的每个结点应该是叶子结点(无孩子)
代码:
代码语言：javascript复制 package com.algorithm.practice.tree;
import java.util.LinkedList;
import java.util.Queue;
public class CompleteBinaryTreeJudge {
public static class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
public static boolean judge(Node head){
if (head==null){
return true;
}
Queue<Node> queue=new LinkedList<>();
boolean leaf=false;//该节点往后的结点是否都为叶子节点标志
Node left=null;
Node right=null;
//如果当前结点左右孩子不全则开启 leaf=true
queue.offer(head);
while (!queue.isEmpty())
{
head=queue.poll();
if (head.right!=null&&head.left==null //有右孩子没左孩子
|| (leaf&&(head.left!=null||head.right!=null))){//开启了全叶子阶段且发现有孩子
return false;
}
if (head.left!=null){
queue.offer(head.left);
}
if (head.right!=null){
queue.offer(head.right);
}
if(head.left==null||head.right==null) { //如果右节点为空
leaf=true; //则后面结点若为完全二叉树,那么只能全为叶子结点
}
}
return true;
}
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.right = new Node(5);
System.out.println(judge(head));
}
}
