递归测试二叉搜索树是否完整

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

}

P.S 所有琐碎的情况都在 isPerfect() 方法中处理，因为每棵完美树也是完整的

Answer 1

我会尝试先记下算法以检查完整性，然后再转到代码。

让我们用预序遍历的方法来考虑这一点。

需要树中的节点数
从根开始递归，将根视为节点索引0
如果节点为空，则树完成
如果节点索引大于（或等于）树中的节点数，则不完整
递归左右子树；给定前序遍历方法，左树得到索引 2*i + 1，右树得到索引 2*i + 2.

对为什么这应该起作用有一点理解。

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

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

一个函数return树中的节点总数

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

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

现在，包装器 isComplete() 函数 [具有 0 个参数，因为根将是一个 class 字段]...

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

Answer 2

我能够与我的教授进行交流，与此处给出的一些答案相比，他告诉我在 isComplete 方法中仅使用一个参数的复杂度为 O(n) 的方法。

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

如果 hR > hL 树不完整。
如果 hL - HR > 1，则树不完整。
如果hR == hL，那么左子树一定是完美的，右子树一定是完整的
否则(hL - hR == 1)，则左子树必须是完美的并且是正确的子树一定要完美。

第 3 步和第 4 步必须递归检查树是否 isPerfect() 和 isComplete()

递归测试二叉搜索树是否完整

Recursivley Test if a Binary Search Tree is complete

java

recursion

binary-search-tree