此问题已经在这里有了答案:
public boolean isBST() {
return isBST(this.root);
}
private boolean isBST(BinaryNode<T> rootNode) {
if (rootNode == null) {
return false;
}
if (rootNode.isLeaf()) {
return true;
}
T left = null;
T right = null;
if (rootNode.hasLeftChild()) {
left = rootNode.getLeftChild().getData();
if (left.compareTo(rootNode.getData()) < 0) {
return this.isBST(rootNode.getLeftChild());
}
else {
return false;
}
}
if (rootNode.hasRightChild()) {
right = rootNode.getRightChild().getData();
if (right.compareTo(rootNode.getData()) > 0) {
return this.isBST(rootNode.getRightChild());
}
else {
return false;
}
}
return true;
}
此代码适用于简单的二叉树,但不适用于其他树。就像我有一棵这样的树:k
5
/ \
3 6
/\
1 2
它甚至不会认为它应该标记为错误,因为2小于3并且在错误的位置。我的代码只检查左孩子的左孩子,而不检查内孩子的右孩子。我怎样做才能使代码以我编写的方式工作?如何修改?
该错误已解决
return this.isBST(rootNode.getLeftChild());
您不能仅因为选中左侧部分(如果存在)而退出该方法。
代替
if (left.compareTo(rootNode.getData()) < 0) {
return this.isBST(rootNode.getLeftChild());
}
else {
return false;
}
这应该符合预期:
if (left.compareTo(rootNode.getData()) >= 0 ||
!this.isBST(rootNode.getLeftChild()) {
return false;
}
(出于对称性原因,您可能还希望以类似的方式重写正确的零件检查,但这不是必需的。您也可以其当前形式工作。)
我认为您需要做的就是递归地看向左和向右,只有在错误的情况下才返回
if (rootNode.hasLeftChild()) {
left = rootNode.getLeftChild().getData();
if (left.compareTo(rootNode.getData()) < 0) {
boolean isValid = this.isBST(rootNode.getLeftChild());
if (!isValid) {
return false;
}
} else {
return false;
}
}
if (rootNode.hasRightChild()) {
right = rootNode.getRightChild().getData();
if (right.compareTo(rootNode.getData()) > 0) {
boolean isValid = this.isBST(rootNode.getRightChild());
if (!isValid) {
return false;
}
} else {
return false;
}
}
return true
看起来,快速检查似乎是在检查右侧之前发生了退货。更为简洁的版本还支持仅在右侧出现重复项(如果您想允许左侧重复项,则将左侧比较中的> =替换为右侧比较中的<=
if (rootNode.hasLeftChild()) {
left = rootNode.getLeftChild().getData();
if (left.compareTo(rootNode.getData()) >= 0) || !this.isBST(rootNode.getLeftChild()) {
return false;
}
}
if (rootNode.hasRightChild()) {
right = rootNode.getRightChild().getData();
if (right.compareTo(rootNode.getData()) < 0 || !this.isBST(rootNode.getRightChild()) {
return false;
}
}
return true;