需要帮助检查二叉树是否是Java中的valis二进制搜索树[重复]

Question

此问题已经在这里有了答案：

• What's the simplest way to print a Java array?33个答案

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并且在错误的位置。我的代码只检查左孩子的左孩子，而不检查内孩子的右孩子。我怎样做才能使代码以我编写的方式工作？如何修改？

Answer 1

该错误已解决

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

（出于对称性原因，您可能还希望以类似的方式重写正确的零件检查，但这不是必需的。您也可以其当前形式工作。）

Answer 2

我认为您需要做的就是递归地看向左和向右，只有在错误的情况下才返回

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;