java - 不带 null 的多态二叉搜索树为 "empty node"

Question

我正在开展一个学校项目，我们必须实现一个多态二叉搜索树，该树不是使用对树的“空”部分的空引用，而是使用两个应该使用多态性的类(NonEmptyTree 和 EmptyTree)确定何时应该采取某些行动。

例如，如果我想在非多态二叉搜索树中插入特定的键值，通常您可以在遍历树时递归地与 null 进行比较，每当您获得的compareTo 值时就坚持您的值0. 然而，在这种情况下，由于这个 EmptyTree 类的设计(它只有一个实例)，您基本上被禁止主动与“EmptyTree.getInstance()”进行比较，“EmptyTree.getInstance()”“释放”了 EmptyTree 的单个实例。 (getInstance() 是静态方法)。

我用迄今为止编写的代码附加了两个类的链接。我认为 Pastebin 的语法突出显示比在这里插入我的所有代码更容易阅读，所以希望这没问题。

我不是在寻找解决方案或任何重大赠品，但我非常沮丧，因为以这种方式实现树似乎不合逻辑。 (我已经实现了一个相当完整的带有空引用的 BST，但似乎这个练习毫无意义，因为我不知道如何继续前进)。此外，这件事要到下周日才能到期，所以我的愤怒根本不是拖延的结果，而是对我个人能力不足的理智挫败感。

任何见解都值得赞赏。

NonEmptyTree 类: http://pastebin.com/

空树类: http://pastebin.com/

正如您所看到的，我广泛使用了 EmptyTree.getInstance() 方法，因为它似乎是一种或多或少有效的方法来检查我是否应该实例化一个新的 NonEmptyList 以粘贴在该位置。然而，教授在项目规范中的话特别指出:“你应该使用多态性(以及适当的异常处理)来处理空树和非空树之间的差异。如果不这样做，将会导致你的项目等级。”

但是，我觉得这些说明与他上学期的讲座相矛盾，其中的信息是“永远不要将异常处理用于“控制流”，即滥用捕获异常作为控制代码行为的方式。”即使是我编写的使用 try-catch block 返回树的单个方法也感觉像是亵渎。

Answer 1

您可能认为这是一个“解决方案”或“重大赠品”，但是......

我同意这看起来有点愚蠢，至少在 Java 中是这样。

不过，这个想法可能是让您的 EmptyTree 和 NonEmptyTree 类继承自某种 PossibleEmptyTree 基类，然后重写每个方法都以不同的方式实现正确的行为，而调用者无需知道(或检查)PossouslyEmptyTree 是否为空(即多态性)。

您的解决方案中可能出现的一些代码:

public class EmptyTree ... {
    ...

    public V search(K key) {
        /* definitely not here! */
        return null;
    }
}