如何验证二叉搜索树？ [英] How to validate a Binary Search Tree?
问题描述
下面是我写来验证BST的code。
是不是正确的？如果没有，我会怎么做呢？
INT的validate（节点*根）
{
如果（根== NULL）回报1;
否则如果（根 - ＆GT; lchild = NULL＆放大器;及（根 - ＆GT; lchild） - ＆GT;！数据＆GT =根 - ＆GT;数据）返回0;
否则如果（根 - ＆GT; rchild = NULL＆放大器;及（根 - ＆GT; rchild） - ＆GT;！数据＆下; =根 - ＆GT;数据）返回0;
验证（根 - ＆GT; lchild）;
验证（根 - ＆GT; rchild）;
返回1;
}
让我们假设你有下面的树：
20
/ \\
10 30
/
15
在根目录开始使用code：
1 INT的validate（节点*根）{
2，如果（根== NULL）回报1;
3否则如果（根 - ＆GT; lchild = NULL＆放大器;及（根 - ＆GT; lchild） - ＆GT;！数据＆GT =根 - ＆GT;数据）返回0;
4其他如果（根 - ＆GT; rchild = NULL＆放大器;及（根 - ＆GT; rchild） - ＆GT;！数据＆下; =根 - ＆GT;数据）返回0;
5验证（根 - ＆GT; lchild）;
6验证（根 - ＆GT; rchild）;
7返回1;
8}
现在前三如果语句（行2至4）根节点不火，因为树的前两级都还好（中左节点小于20和右节点大于20）。所以，你再试图通过递归调用第5行，以验证左子树（包含10个节点）。
在这一号召，它的不的，因为它的左节点好吗（15）大于它和一行三会返回零，表示这是不好的。
不过，因为你叫验证和扔掉的返回值，它只是进行6行那么最终的返回1那最后的第7行，即使树的不的有效。
您需要做的是向下级传递结果到上水平，使他们能够在采取行动。
您还可以摆脱那些否则，如果的事情，因为他们是没用以下一回，我没有使用可变的大风扇根在这种情况下，因为它只有扎根于递归的顶层（它可能会混淆一些）。
我会去喜欢的东西（在适当的注释）：
INT的validate（节点* testNode）{
//终端的情况下，空的子树是有效的。 如果（testNode == NULL）
返回1; //左节点＆GT; =电流意味着无效 如果（testNode-＆GT;！lchild = NULL）
如果（testNode-＆GT; lchild-＆GT;数据GT＆= testNode-＆GT;数据）
返回0; //对节点＆lt; =电流意味着无效 如果（testNode-＆GT;！rchild = NULL）
如果（testNode-＆GT; rchild-＆GT;数据＆LT; = testNode-＆GT;数据）
返回0; //无效的整个左子树表示无效。 如果（！的validate（testNode-＆GT; lchild））
返回0; //否则返回整个右子树的状态。
返回的validate（testNode-＆GT; rchild）;
}
您可能还需要考虑一下你是否在你的树要重复的值。如果你这样做，攀比应＆LT; 和＆GT; ，而不是＆LT; = 和方式＆gt; =
Here is the code that I have written to validate a BST.
Is it correct? If not, how would I do this?
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;
}
Let's say you have the following tree:
20
/ \
10 30
/
15
and start at the root with your code:
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 }
Now the first three if statements (lines 2 through 4) don't "fire" at the root node because the first two levels of the tree are okay (the left node is less than 20 and the right node is greater than 20). So you then try to validate the left subtree (the node containing 10) by a recursive call at line 5.
In that call, it's not okay since its left node (15) is larger than it is and line 3 will return zero to indicate it's bad.
However, because you've called validate and thrown away the return value, it simply carries on to line 6 then eventually returns 1 on that final line 7, even though the tree is not valid.
What you need to do is to to pass up the lower level results to the upper levels so that they can be acted upon.
You can also get rid of those else if things since they're useless following a return, and I'm not a big fan of using the variable root in this case since it's only root at the top level of the recursion (it may confuse some).
I'd go with something like (with appropriate comments):
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);
}
You may also want to think about whether you want duplicate values in your tree. If you do, the comparisons should be < and > rather than <= and >=.
这篇关于如何验证二叉搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
