检查二叉树是否为二叉搜索树的函数？

-1

我试图写下面的方法来告诉二叉树是否是二叉搜索树？我只通过了一半的测试用例。我究竟做错了什么？检查二叉树是否为二叉搜索树的函数？

boolean checkBST(Node root) { 

    boolean leftflag = false; 
    boolean rightflag = false; 

    Node l = root.left; 
    Node r = root.right; 

    if(l!=null) { 
     if(root.data <= l.data) { 
      leftflag = false; 
     } 
     else { 
      leftflag = true; 
      checkBST(l); 
     } 
    } 
    if(leftflag == false) 
     return false; 
    if(r != null) { 
     if(root.data >= r.data) { 
      rightflag = false; 
     } 
     else { 
      rightflag = true; 
      checkBST(r); 
     } 
    } 
    if(rightflag == false) 
     return false; 

    return true; 
}

来源

2016-10-04 Abhishek Sharma

欢迎StackOverflow上。请阅读并遵守帮助文档中的发布准则。 [最小，完整，可验证的示例]（http://stackoverflow.com/help/mcve）适用于此处。在您发布代码并准确描述问题之前，我们无法有效帮助您。具体来说，你的发布代码什么都不做：没有测试驱动程序。此外，您未能证明失败的案例。 – Prune

我可以看到你的程序错误地返回错误的情况。

想象一下，你有3个分支深要去如下树：

你的程序在7（根）启动，创建于假两个布尔（leftflag和rightflag），检查剩下的就是空。事实并非如此。然后它检查左边的数据< =右边的数据。它是。

所以你用一个新的根节点（例子中的3）递归地调用你的函数。再次，它创建你的两个布尔值为假初始值，检查左节点是否为空。它是！因此，如果在返回之前直接转到其他人，则会跳过整个项目。

// The condition here is respected, there is no left node 
// But the tree is an actual search tree, you didn't check right node 
// Before returning false. 
if(leftflag == false) 
    return false

什么，我会做的是

if(l != null) 
{ 
    if(root.data<=l.data) 
    { 
     return false; 
    } 
    else 
    { 
     // recursive call here 
    } 
} 

if(r != null) 
{ 
    // Same as left node here 
}

所以即使你的左节点为空，程序仍检查右节点。希望我帮助一点点！

来源

2016-10-04 14:57:38 Scriptodude

您的主要错误是您忽略了递归调用的返回值。例如：

else { 
     leftflag = true; 
     checkBST(l); 
    } 
} 
if(leftflag == false) 
    return false;

如果checkBST（l）返回false，则忽略它。你永远不会保存价值。因此，您之后对左标志的检查完全不了解子树的适用性。在语义上，你的例程假定所有的子树都是BST--你设置了标志，在子树上重复出现，但是不要改变标志。试试这个逻辑：

else 
    leftflag = checkBST(l)

现在，请让舒适的布尔表达式。例如，对布尔常量测试一个布尔值是有点浪费的。取而代之的

if (flag == false)

就直接检查：

if (!flag)

检查空指针，在大多数语言类似：

if (l)

最后，如果你不初始化标志简单地将它们设置为与第一个动作相同的值。现在

，你的代码可能会出现这样的：

boolean leftflag = false; 
    boolean rightflag = false; 

    if(l) { 
     if(root.data > l.data) { 
      leftflag = checkBST(l); 
     } 
    } 
    if(!leftflag) 
     return false; 

    if(r) { 
     if(root.data < r.data) { 
      rightflag = checkBST(r); 
     } 
    } 
    if(rightflag == false) 
     return false; 

    return true; 
}

现在，这是一个比较容易遵循逻辑流程。请注意，您在基本情况下有一个基本失败：空树为平衡，但您返回错误。

现在，如果你愿意了解更多关于逻辑短路和布尔表达式，您可以将日常减少到更多的东西是这样的：

return 
    (!root.left ||   // Is left subtree a BST? 
     (root.data > root.left.data && 
     checkBST(root.left))) 
    && 
    (!root.right ||   // Is right subtree a BST? 
     (root.data > root.right.data && 
     checkBST(root.right)))

来源

2016-10-04 16:20:04 Prune

检查二叉树是否为二叉搜索树的函数？

回答

相关问题