如何檢查一棵樹是否是BST？

我要檢查，如果樹是二叉搜索樹。我正在用一個臨時數組進行inorder遍歷來完成這項工作，該臨時數組收集這些值。我要檢查，如果數組是按升序排列，如果它是那麼我返回true：如何檢查一棵樹是否是BST？

bool myisBST(Node* node, std::vector<int> v); 

bool myisBST(Node* node) 
{ 
    return myisBST(node, std::vector<int>()); 
} 

bool myisBST(Node* node, std::vector<int> v) 
{ 
    if (node) 
    { 
     if (node->left) 
      return myisBST(node->left, v); 

     v.push_back(node->data); 

     if (node->right) 
      return myisBST(node->right, v); 
    } 

    return std::is_sorted(v.begin(), v.end()); 
}

當二叉樹是這樣的：

  50 
     /\ 
     25 75 
     /\ /\ 
     1 12 62 -99

正如你所看到的，-99使這不是一個二叉搜索樹，但它仍然返回true。我的實現有什麼問題嗎？

Demo

來源

2014-12-01 template boy

'-99'使它不是二叉查找樹，但它仍然返回true。你的實現有什麼問題嗎？你有沒有更好的人選可能是錯的？ – juanchopanza 2014-12-01 21:25:42

@juanchopanza再來一次？ – 2014-12-01 21:33:20

在調試器中運行你的程序，看看它需要什麼執行路徑。您的代碼嗟已排序檢查 – Vladimir 2014-12-01 21:34:17

兩個問題：

在myisBST，你是值傳遞v，而不是引用，所以當你通過遞歸的載體，即所進行的更改它不會在調用方法中改變它的值。只需將功能簽名更改爲bool myisBST(Node* node, std::vector<int>& v)即可解決此問題。
您應該返回的值是矢量是否排序（如您在方法的最後一行中所做的那樣），而是通過編寫return myisBST(node->left, v);和return myisBST(node->right, v);過早返回。你實際上並不關心這些方法的返回值;你只是用它們來填充矢量。從這兩行刪除return。

隨着這兩個補丁，你的方法效果。

來源

2014-12-01 21:40:36

謝謝，這個作品。 – 2014-12-01 21:45:33

首先，你應該通過引用傳遞vector或每次遞歸調用將得到一份拷貝，因此原來的載體可能是空的。第二，你甚至不需要先創建矢量然後再做檢查，你可以在每個節點檢查BST屬性，也就是說，根必須大於左邊的小孩，小於右邊的孩子，例如，

bool isBST(const Node* root, vector<int>* v) { 
    if (!root) { return true; } 

    bool leftBST = true; 

    if (root->left) { 
    if (root->data > root->left->data) { 
     leftBST = isBST(root->left, v); 
    } else { 
     // the current node violates the BST precondition 
     return false; 
    } 
    } 

    // push the root 
    v->push_back(root->data); 
    // return false if left subtree is not a BST 
    if (!leftBST) return false; 

    if (root->right) { 
    if (root->data < root->right->data) { 
     // return whether or not the right subtree is a BST 
     return isBST(root->left, v); 
    } else { 
     // the current node violates the BST precondition 
     return false; 
    } 
    } 

    // everything good, this is a BST 
    return true; 
}

來源

2014-12-01 21:51:38

如何檢查一棵樹是否是BST？

回答

相關問題