完全二叉树的判定

Posted on In Views: Views:

树节点类

1
2
3
4
public class Node {
  Object Data;
  Node left,right,parent;
}

二叉树类

其中judge方法为判断是否是完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class BinTree {
  Node root;
  public boolean judge() {
    int n0 = 0, n = 0, stage = 1;
    if (this.root == null)
      return true;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(this.root);
    while (!queue.isEmpty()) {
      Node node = queue.poll();
      n++;
      //三个必要条件之一
      if (node.left == null && node.right != null)
        return false;
      //三个必要条件之二
      if (stage == 2 && (node.left != null || node.right != null))
        return false;
      stage = (node.left != null && node.right == null) ? 2 : stage;
      if (node.left != null)
        queue.offer(node.left);
      if (node.right != null)
        queue.offer(node.right);
      if (node.left == null && node.right == null) {
        n0++;
        stage=2;
      }
    }
    //三个必要条件之三：完全二叉树满足的公式n0=n/2，其中n0是度为0的节点，n是树总的节点数
    return (n0 == (int) Math.ceil(n / 2.0)) ? true : false;
  }
}