java полиморфное двоичное дерево поиска

Question

Как реализовать полиморфное двоичное дерево поиска (которое использует EmptyTree и NonEmptyTree) без использования downcasting или проверки класса?

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» может просто ссылаться на своих дочерних элементов через общий интерфейс и полагаться на то, что тип выполнения будет правильным. (при этом нет необходимости выполнять кастинг или проверку типов детей при реализации алгоритма).

Единственное место, где вам нужно знать тип выполнения, - это когда вы создаете детей.