如何驗證二進制搜索樹？

它是正確的嗎？如果不是，我將如何做到這一點？

int validate(node *root) 
{ 
    if(root==NULL) return 1; 
    else if(root->lchild!=NULL && (root->lchild)->data >=root->data) return 0; 
    else if(root->rchild!=NULL && (root->rchild)->data <=root->data) return 0; 
    validate(root->lchild); 
    validate(root->rchild); 
    return 1; 
}

來源

2012-03-12 mmuttam

可能重複[如何最高值你驗證二叉搜索樹？]（http://stackoverflow.com/questions/499995/how-do-you-validate-a-binary-search-tree） – Dukeling 2014-06-17 11:59:01

比方說，你有以下三種：

，並在你的代碼根本入手：

1 int validate(node *root) { 
2  if(root==NULL) return 1; 
3  else if(root->lchild!=NULL && (root->lchild)->data >=root->data) return 0; 
4  else if(root->rchild!=NULL && (root->rchild)->data <=root->data) return 0; 
5  validate(root->lchild); 
6  validate(root->rchild); 
7  return 1; 
8 }

現在前三if語句（行2至4）不要在根節點「開火」，因爲樹的前兩個級別都可以（左節點小於20，右節點大於20）。所以，你再嘗試通過遞歸調用在第5行

驗證左子樹（含10點），在這一號召，這是不沒關係，因爲它的左節點（15）大於它與線3將返回零來表示它不好。

但是，因爲你叫validate和扔掉返回值，它只是進行到第6行，然後最終上最後一行7返回1，即使樹是不是有效。

你需要做的是將較低級別的結果傳遞到較高級別，以便他們可以採取行動。

你也可以擺脫那些else if的東西，因爲它們在返回後毫無用處，在這種情況下，我並不喜歡使用變量root，因爲它只是遞歸頂層的根（它可能會混淆一些）。

我會去喜歡的東西（在適當的註釋）：

int validate (node *testNode) { 
    // Terminal case, empty sub-tree is valid. 

    if (testNode == NULL) 
     return 1; 

    // Left node >= current means invalid 

    if (testNode->lchild != NULL) 
     if (testNode->lchild->data >= testNode->data) 
      return 0; 

    // Right node <= current means invalid 

    if (testNode->rchild != NULL) 
     if (testNode->rchild->data <= testNode->data) 
      return 0; 

    // Invalid entire left subtree means invalid. 

    if (! validate (testNode->lchild)) 
     return 0; 

    // Otherwise return state of entire right subtree. 
    return validate (testNode->rchild); 
}

您可能還需要考慮是否在你的樹要重複的值。如果這樣做，比較應該是<和>而不是<=和>=。

來源

2012-03-12 13:19:15 paxdiablo

考慮樹

10 
/\ 
8 15 
/\ /
3 9 4

在這棵樹，到處root->left->data < root->data和root->right->data > root->data。

但樹不是BST，因爲節點4不在正確的位置（它大於10，這是無效的）。

如果你有驗證BST，你應該能夠找出條件：

在左子樹<最低值是右子樹的

來源

2012-10-15 21:06:34 PCoder

如何驗證二進制搜索樹？

回答

相關問題