我知道这是一个非常具体的问题，但我不太确定如何更宽泛地表达它，所以如果您在这里认识到更宽泛的问题，请回答它。我已经实现了大部分 BinarySearchTree 类，但我不确定在哪里进行检查以确保它是有效的 BinarySearchTree。目前我没有检查，但我正在考虑在该树上的每个相关操作之前检查(即搜索前检查、树遍历之前检查、minimum 之前检查等)以及树何时被构造。如果树无效，那么我将抛出一个 IllegalArgumentException。然而，在我实现这个之前，我考虑创建一个新的 BinarySearchTreeNode 类来扩展 BinaryTreeNode (这是我当前正在使用的类)，而不是在 BinarySearchTreeNode 类(在构造时和设置子项时)。 所以，我不需要任何这些的实现(我已经有一个 isValidBinaryTree 方法)，但这是最佳实践:从不检查树是否有效，检查树是否有效在树的构建期间和树上的每个方法调用之前是否有效，或者创建一个 BinarySearchTreeNode 类在构建期间和子节点设置时进行检查？
仅供引用，您真的不需要知道二叉搜索树是什么。它只是一种二叉树(每个节点有 0-2 个子节点)，其中左子节点的值 <= 父节点的值，右子节点的值 >= 所有节点的父节点的值在树中(这就是我所说的有效树)。
最佳答案
你的类(class)会有契约(Contract)。对二叉搜索树的合理期望是每个这样的树确实是一棵二叉搜索树。这称为不变。
操纵这样一棵树的每个操作都应该以这种不变量永不破坏的方式进行。
这意味着对于每个操作，您需要确保当方法完成时，该对象仍然代表一个二叉搜索树，所有不变量都完好无损。
当然，您可以通过选择 API 使这对您来说变得容易或困难。如果您的树向公众公开允许破坏不变量的内部方法，那么您的设计已损坏。
因此，您应该以这样一种方式设计您的公共(public) API，即您确实可以为每个公共(public)方法保留不变量。
例如，空树确实是一棵二叉搜索树。如果您的 add 和 remove 方法确保不变量成立(并且不存在其他操纵树状态的方法)，那么根本没有理由在搜索之前检查这些不变量是否为真。如果你做对了，你可以写一个证明它们在那个时候必须是真的。
关于java - 在二叉搜索树中的何处添加有效性检查，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38978479/