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”类可以通过公共接口简单地引用其子级，并依赖于运行时类型将做正确事情的事实（因此在执行该算法时不需要进行任何铸造或类型检查）。

您需要知道运行时类型的唯一地方是在构建子代时。