java - java多态二叉搜索树

Question

如何在不使用向下转换或类检查的情况下实现多态二叉搜索树（使用 EmptyTree 和 NonEmptyTree）？

Answer 1

创建一个通用接口，例如：

interface TreeNode<K, V> {
   TreeNode<K, V> find(K key)
}

然后提供实现通用接口的类：

class EmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K key) {
      // ...
   }
}

class NonEmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K searchKey) {
      // ...
   }
}

您的 EmptyTree 实现将始终指示搜索项目失败（无论是通过返回 null 还是通过引发异常），而您的 NonEmptyTree 实现将返回自身（如果提供的搜索键匹配）或委托给左侧或右子树。因为左子树或右子树将始终存在（它将是 NonEmptyTree 或 EmptyTree），“NonEmptyTree”类可以通过公共接口简单地引用其子树，并依赖于运行时类型将做正确的事情这一事实（因此在算法的实现中没有必要对孩子进行任何强制转换或类型检查）。

唯一需要知道运行时类型的地方是在构造子项时。