Recursivley测试二进制搜索树是否完整

Question

前几天我问了一个关于同一个项目的问题，从那时起我们的小组已经设法完成了我们所有的方法，除了一个用于确定二叉搜索树是否是完成。

我们使用一个包装方法和一个辅助方法递归地做到这一点。

我们知道我们需要检查树的h-1层（h是高度）以确保它是完美的，那么我们需要确保最后一层上的所有叶节点都从左边开始没有差距的权利。

无论我们尝试什么，我们都无法弄清楚如何递归检查剩余的叶节点，以确保它们从左到右依次连续。但是，我们可以确保它完美达到（h-1）级别。

有人能指出我们在正确的方向上如何递归检查最后一级的叶节点，以确保它们左对齐吗？

迄今为止这是代码？

public boolean isComplete() 
{ 
    if (isPerfect(root)) 
     return true;  
    return isComplete(root); 

} 
/** 
* 
* @param node 
* @return 
*/ 
private boolean isComplete(Node node) 
{ 
    if (height(node) > 1) 
    { 
    if (node.left != null && node.right != null && (height(node.left) == height(node.right))) 
     return isComplete(node.left) && isComplete(node.right); 
    else 
     return false; 
    } 

} 

PS，因为每一个完美的树中的所有琐碎的案件在isPerfect（）方法处理也完全

Answer 1

我能够与我的教授进行交流，并且他告诉MOF只有一个在isComplete方法参数做它的O（n）的方式相比，这里给出一些答案。

这个答案这里是我原来的问题

1. 如果HR>百升树是不完整的最好的答案。
2. 如果hL-HR> 1，树不完整。
3. 如果HR == HL，然后左子树必须是完美的，右子树必须完整
4. 否则（HL - HR == 1），则左子树 必须是完美的，右子树 绝完美。

步骤3和4必须递归检查树isPerfect（）和isComplete（）

Answer 2

我会尝试第一个音符的算法来检查完整性，然后移动到代码。

让我们在预定义遍历方法中考虑这一点。

• 需要的节点的数量在树
• 递归从根，治疗根作为节点索引0
• 如果节点为空，树是完整
• 如果节点索引大于（或等于）树中节点的数量，则不完整
• 递归左右子树;给定预定义遍历方法，左树得到索引2*i + 1，右树得到2*i + 2。

有一点理解为什么这应该工作。

以下是一棵完整的树[带方括号中的节点索引]。 请注意，此完整二叉树的节点索引严格少于完整二叉树中的节点数。

  1 [0] 
     /\ 
     / \ 
    [1] 2  3 [2] 
    /\ 
    / \ 
[3] 4  5 [4] 

甲函数返回节点的总数目在树现在

private int totalNodes(Node root) { 
    if (root == null) 
     return 0; 

    return 1 + totalNodes(root.left) + totalNodes(root.right)); 
} 

，包装器isComplete（）函数[0参数，由于根是一类字段] ...

public boolean isComplete() { 
    return isCompleteHelper(root, 0, totalNodes(root)); 
} 

isCompleteHelper（）...

private booelan isCompleteHelper(Node root, int indx, int totalNodes) { 

    // empty tree 
    if (root == null)   
     return true; 

    // present index >= number of nodes in tree 
    if (indx >= totalNodes) 
     return false; 

    // recurse 
    return isCompleteHelper(root.left, 2*indx+1, totalNodes) && isCompleteHelper(root.right, 2*indx+2, totalNodes); 
}