如何validation二进制搜索树？
这是我为validationBST而编写的代码。
这是对的吗？ 如果没有，我该怎么做？
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 data) return 0; validate(root->lchild); validate(root->rchild); return 1; } 假设你有以下树：
20 / \ 10 30 / 15
并使用您的代码从根开始：
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行的递归调用validation左子树（包含10的节点）。
在那个调用中，它不合适，因为它的左节点（15）比它大，而第3行将返回零以指示它是坏的。
但是，因为你已经调用了validate并抛弃了返回值，它只是继续执行第6行，然后最终在最后一行7返回1，即使树无效。
你需要做的是将较低级别的结果传递给较高级别，以便对它们采取行动。
else if因为返回后它们没用，你也可以摆脱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); }
您可能还想考虑是否需要树中的重复值。 如果这样做，则比较应为<和>而不是<=和>= 。
考虑树
10 / \ 8 15 / \ / 3 9 4
在这棵树中，到处都是root->left->data < root->data和root->left->data < root->data root->right->data > root->data 。
但是树不是BST，因为节点4不在正确的位置（它大于10 ，这是无效的）。
如果您必须validationBST，您应该能够找出条件：
- 左子树中的最高值<最低值是右子树