如何驗證給定的樹是否爲二叉搜索樹

我不知道該怎麼做呢？

我所知道的唯一的事情就是BST意志的序遍歷爲您提供了升序輸出。

所以，這是我們需要驗證或者是還有什麼事情，我們想檢查的唯一條件。

在情況下，如果有要檢查其他一些必要條件，它們是什麼？以及爲什麼這些條件需要檢查？因爲，我認爲，如果給定的樹是BST，INORDER遍歷本身可以很容易地告訴你。

2012-04-16 Jatin

開始[二叉搜索樹的定義（http://en.wikipedia.org/wiki/Binary_search_tree）。給出的樹是否符合這個定義？（請注意，按順序遍歷規則可以通過遞歸地應用規則來導出。還要注意，不同的樹，例如RB，可能有資格作爲BST *和*另一種樹類型。） – 2012-04-16 08:44:35

（或者說，RB樹*是a * BST等） – 2012-04-16 08:51:06

請問您可以通過下面的鏈接....我問的問題幾乎與此類似。但在這個環節中，除了INORDER遍歷之外，人們還提出了其他一些方法。我不知道爲什麼這些額外的條件需要檢查。 http://stackoverflow.com/questions/499995/what-is-validating-a-binary-search-tree – Jatin 2012-04-16 09:02:01

是的，如果序樹的遍歷給你值的嚴格單調名單足以確定該樹是BST。

來源

2012-04-16 08:42:19

它可以重複嗎？單調列表是什麼意思？ – 2017-04-22 14:40:35

通過二叉搜索樹的定義，若二叉樹的每個節點滿足下列條件那麼它是一個二叉搜索樹：

一個節點的左子樹應該只包含節點與鍵小於節點的密鑰
節點的右側子樹應只包含密鑰大於節點密鑰的節點
左側和右側子樹也必須是二叉搜索樹。

如果按順序遍歷按升序排列，則所有上述條件都被驗證。

來源

2013-03-05 16:04:23 banarun

其實 - 這是不夠的，只是做一箇中序遍歷 - 你還需要驗證每個節點的值如下樹的規則。在BST的情況下，左側子值小於節點值，右側子值大於節點值。這是Java中的遞歸示例。

private static boolean isBST(Node current, Comparable more, Comparable less) { 
    if (current == null) 
     return true; 

    if (less != null && current.value.compareTo(less) > 0) 
     return false; 

    if (more != null && current.value.compareTo(more) < 0) 
     return false; 

    return isBST(current.left, more, current.value) && 
      isBST(current.right, current.value, less); 
} 

public static boolean isBST(BinarySearchTree tree) { 
    return isBST(tree.getRoot(), null, null); 
}

來源

2013-08-27 13:57:04

While doing In-Order traversal, we can keep track of previously visited node

代碼：

bool isBST(struct node* root) 
{ 
    static struct node *prev = NULL; 

    // traverse the tree in inorder fashion and keep track of prev node 
    if (root) 
    { 
     if (!isBST(root->left)) 
      return false; 

     // Allows only distinct valued nodes 
     if (prev != NULL && root->data <= prev->data) 
      return false; 

     prev = root; 

     return isBST(root->right); 
    } 

    return true; 
}

來源

2014-05-09 07:12:29 Suraj

Java中的簡單而優雅的遞歸解決方案：

public static boolean isBST(TreeNode node, int leftData, int rightData) 
{ 
    if (node == null) return true; 

    if (node.getData() > leftData || node.getData() <= rightData) return false; 

    return (isBST(node.left, node.getData(), rightData) 
      && isBST(node.right, leftData, node.getData())); 

}

這個函數的初始呼叫可以是這樣的：

if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE)) 
    System.out.println("This is a BST."); 
else 
    System.out.println("This is NOT a BST!");

本質上，我們一直創建一個有效範圍（從[MIN_VALUE，MAX_VALUE]開始），並在遞歸下降時保持每個節點收縮。

來源：http://exceptional-code.blogspot.com/2011/08/binary-search-trees-primer.html

來源

2014-05-09 21:30:28 Sanj

如何驗證給定的樹是否爲二叉搜索樹

回答

相關問題