二叉树6:判断一棵树是否是完全二叉树
完全二叉树:所谓完全二叉树是指除了最后一层之外,其他每一层的结点数目都是满的,如果最后一层也满了就是满二叉树,如果最后一层不满那么结点全部集中在左侧,从左侧开始补齐。满二叉树是一棵特殊的完全二叉树,对于完全二叉树这种特殊的结构,它可以使用数组来表示各个结点,此时每个结点与它的子节点的位置下标之间存在直接的对应关系,即从数组中i=1开始存放元素,于是对于某个结点i,它的左孩子下标是2i,它的右孩子结点时2i+1,它的父节点下标是i/2。堆(优先队列)就是一种完全二叉树结构。
思想:不是完全二叉树数有如下几种情况:
通过按层遍历二叉树的方法来判断一棵二叉树是不是完全二叉树;
代码:
public class isCBT{
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
Queue<Node> queue = new LinkedList<Node>();//DQ双端链表可以实现队列
boolean leaf = false;
Node l = null;
Node r = null;
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
//((leaf && (l != null || r != null)) 意思是如果它应该是叶子节点但是它还有左右孩子,返回false
//例如 2已经是叶子节点了,那么它的父节点的右子树也应该是一个叶节点
if ((leaf && (l != null || r != null)) || (l == null && r != null)) { //如果没有左孩子,有右孩子返回false;如果左右孩子有一个为null,那么后面的节点一定要是叶子节点,否则返回false
return false;
}
if (l != null) {
queue.offer(l);
}
if (r != null) {
queue.offer(r);
} else { //这里的条件就是左右都是null 为叶子节点
leaf = true;
}
}
return true;
}
}