算法，检查树是否已满并完成

我想编写一个方法，如果二叉树已满并且完成（每个节点有2个childern或没有并且树的所有叶都在相同的深度）。算法，检查树是否已满并完成

我的想法是使用递归。我会检查任何节点，如果它的儿子有一定数量的childern，这是它的正确的儿子的数字childern。如果是这样 - 我将返回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; 
    } 
}

我没有把树实现，但它是非常简单的。

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

你认为我的alogrithem是相关还是我错过了什么？

非常感谢。

来源

2015-04-29 Matoy

这可以以更简单的方式完成;但我相信这应该在代码审查而不是在这里 – fge

我不问关于代码，因为我正在问关于算法的正确性。怎么样？在复杂性方面？我认为这是非常好的o（n） - 因为n是节点的数量。 – Matoy

你应该更好地发布你的算法的伪代码。恕我直言，它更清晰的阅读。 –

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

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)

通过你的定义，“完全彻底”是指“每节点有2个孩子或没有，并且树的所有树叶都在相同的深度“

因此，如果两个子树都是”完整且完整的“，并且它们具有相同数量的节点（假设它是M），那么通过Lemma 1，这两个子树的所有叶子都会有s ame depth = log2(M+1)，它们在原树中的深度都将是log2(M+1) + 1。

而且根有两个孩子，再加上两个子树都是“完整的”，意味着所有的笔记都有两个孩子或没有孩子。然后根据定义，原始树也是“完整和完整的”。

再次，正如fge @提到的，这可以以更简单的方式实现。就像检查最大深度== log2（N-1）

来源

2015-04-29 20:07:13 lavin

算法，检查树是否已满并完成

回答

相关问题