java - 检查树是否完整的算法

Question

我正在尝试编写一个方法，如果二叉树已满且完整(每个节点有 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 的数量。如果树不完整且不完整 - 那么在某些节点中，此规则将不适用。

您认为我的算法是否正确，还是我遗漏了什么？

非常感谢。

Answer 1

我认为您要求对您的算法进行更多的数学证明。你的算法是正确的。证明可以简单地使用演绎来完成。

引理 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)