檢查二叉樹是否爲二叉搜索樹的函數？

-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

檢查二叉樹是否爲二叉搜索樹的函數？

回答

相關問題