Willow's blog

完全二叉树的判定

树节点类

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;
}
}
(EOF)
杨威
发布日期 :2017-01-20
自由转载-非商用-非衍生-保持署名(知识共享3.0许可证)
杨威 wechat
微信订阅号
写点什么 心里不慌