我正在尝试编写一个方法,如果二叉树已满且完整(每个节点有 2 个子节点或没有,并且树的所有叶子都在相同深度),该方法将返回 true。
我的想法是使用递归。我将检查任何节点,如果它的左儿子的 child 数量等于它的右儿子的 child 数量。如果是 - 我将返回 true,否则返回 false;
算法将如下所示:
public class Utils {
public boolean isFullCompleteTree(Tree<Integer> t) {
TreeInfo rootInfo = isFullCompleteTree(t.getRoot());
return rootInfo.valid;
}
public TreeInfo isFullCompleteTree(Node<Integer> node) {
boolean valid = true;
if (node == null) {
return new TreeInfo(true, 0);
}
TreeInfo rightInfo = isFullCompleteTree(node.goRight());
TreeInfo leftInfo = isFullCompleteTree(node.goLeft());
if ((!rightInfo.valid) || (!leftInfo.valid)) {
valid = false;
}
if (rightInfo.numChildern != leftInfo.numChildern) {
valid = false;
}
return new TreeInfo(valid, rightInfo.numChildern + leftInfo.numChildern
+ 1);
}
}
class TreeInfo {
public boolean valid;
public int numChildern;
public TreeInfo(boolean valid, int numChildern) {
this.valid = valid;
this.numChildern = numChildern;
}
}
我没有放置树的实现,但它非常简单。
该算法的思想是检查每个节点中右儿子的 child 的数量是否等于左儿子的 child 的数量。如果树不完整且不完整 - 那么在某些节点中,此规则将不适用。
您认为我的算法是否正确,还是我遗漏了什么?
非常感谢。
最佳答案
我认为您要求对您的算法进行更多的数学证明。你的算法是正确的。证明可以简单地使用演绎来完成。
引理 1:
如果一棵完整的二叉树的节点数等于 N
,则它的叶子深度为log2(N+1)
这个引理本身可以通过演绎来证明:
对于N = 1
,它是正确的。
对于N > 1
,它的左右子树各有(N-1)/2
个节点,并且都有深度的叶子= log2((N-1)/2+1)
,所以现在深度将为 log2((N-1)/2+1) + 1 = log2(((N-1)/2+1) * 2) = log2(N-1 + 2) = log2(N+1)
根据您的定义,“完整且完整”意味着“每个节点有 2 个子节点或没有子节点,并且树的所有叶子都处于相同的深度”
因此,如果两个子树都是“完整且完整”的,并且它们具有相同数量的节点(比如说是M
),那么通过Lemma 1
,两个子树中的所有叶子将具有相同的 depth = log2(M+1)
,并且它们在原始树中的深度将全部为 log2(M+1) + 1
。
并且根节点有 2 个子节点,加上两个子树都是“完整且完整”的,这意味着所有注释都有 2 个子节点或没有。那么根据定义,原始树也是“完整的”。
再一次,正如 fge@ 提到的,这可以用更简单的方式实现。就像检查最大深度是否 == log2(N-1)
关于java - 检查树是否完整的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29952056/