检查树是否为满二叉树和完全二叉树的算法

Question

我想编写一个方法，如果二叉树是完整和饱和的（每个节点有两个子节点或没有子节点，并且树的所有叶子节点都在相同的深度），则返回true。

我的想法是使用递归。我将检查任何节点，如果它的左儿子具有与其右儿子相等的子节点数，则返回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;
    }
}

我没有放置树的实现，但它非常简单。

算法的思路是检查每个节点中右子孙的数量是否等于左子孙的数量。如果一棵树不完整或不完全，则在某些节点上此规则将不适用。

你认为我的算法正确吗？或者我遗漏了什么？

非常感谢。

- Matoy

---

这可以用更简单的方式完成；但我认为这应该在代码审查中进行，而不是在这里。 - fge

我不是在问代码，而是在问算法的正确性。还有，简单来说，复杂度如何？我认为它相当不错，是O(n)——其中n是节点数。 - Matoy

如果代码“按预期工作”，并且您正在寻求改进，您可以在Code Review网站上发布，并从Stack Overflow中删除它。如果这样做，最好包括您的树实现。 - Phrancis

@user1007665 验证你的实现的最佳方法是编写单元测试（查看Junit），检查您的代码在各种输入下的输出。通常，如果您能编写并运行测试，就可以确定算法是否正确。 - Luke Willis

为什么要一次执行两个检查？定义两个方法，每个方法执行一个检查，然后将它们组合起来... - Willem Van Onsem

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），那么根据引理1，两个子树中的所有叶子节点都将具有相同的深度= log2(M+1)，它们在原始树中的深度都将是log2(M+1)+1。

而且，根节点有两个子节点，加上两个子树都是“完整的”，这意味着所有节点都有2个子节点或没有子节点。那么根据定义，原始树也是“完整的”。

而且，正如fge@所提到的，这可以用更简单的方法实现。比如只需检查最大深度是否等于log2(N-1)。

- lavin