如何验证二进制搜索树？

它是正确的吗？如果不是，我将如何做到这一点？

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

如何验证二进制搜索树？

回答

相关问题