检查树是否完整的算法

Question

我正在尝试编写一种方法，如果二叉树已满且完整（每个节点有 2 个子节点或 none 并且树的所有叶子都在相同的深度）。

我的想法是使用递归。我将检查任何节点，如果它的左儿子的孩子数量等于它的右儿子的孩子数量。如果是 - 我将 return 为真，否则为假；

算法将如下所示：

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;
    }
}

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

该算法的思想是检查每个节点中右儿子的孩子数是否等于左儿子的孩子数。如果树不完整且不完整 - 那么在某些节点中，此规则将不适用。

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

非常感谢。

Answer 1

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

Lemma 1:如果一棵完整的二叉树的节点数等于N，那么它的叶子深度为log2(N+1)

这个引理本身可以通过演绎来证明：

对于 N = 1 这是正确的。

对于N > 1，它的左右子树各有(N-1)/2个节点，都有depth = log2((N-1)/2+1)个叶子，所以现在深度为log2((N-1)/2+1) + 1 = log2(((N-1)/2+1) * 2) = log2(N-1 + 2) = log2(N+1)

根据您的定义，"full and complete" 表示 "each node has 2 children or none and all the leaves of the tree are at the same depth"

所以如果两个子树都是"full and complete"，并且它们有相同数量的节点（假设是M），那么通过Lemma 1，两个子树中的所有叶子都将具有相同的depth = log2(M+1)，并且它们在原始树中的深度都将是log2(M+1) + 1。

并且根节点有 2 个子树，加上两个子树都是 "full and complete" 意味着所有音符都有 2 个子节点或 none。那么根据定义，原始树也是 "full and complete".

而且，正如 fge@ 提到的，这可以通过更简单的方式实现。就像检查最大深度是否 == log2(N-1)

检查树是否完整的算法

algorithm that checks if a tree is full and complete

java

algorithm

tree

recursion