如何验证二进制搜索树？

Question

这是我为验证BST而编写的代码.

这是对的吗？如果没有,我该怎么做？

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;
}

Answer 1

考虑树

    10
   /  \ 
 8    15
/ \   /
3  9 4 

在此树,到处root->left->data < root->data和root->right->data > root->data.

但是树不是BST,因为节点4不在正确的位置(它大于10,它是无效的).

如果您必须验证BST,您应该能够找出条件:

• 左子树中的最高值<最低值是右子树