arbre de recherche binaire polymorphe java

Question

Comment puis-je implémenter un arbre de recherche binaire polymorphe (qui utilise EmptyTree et NonEmptyTree) sans utiliser de downcasting ou de vérification de classe?

Answer 1

Créer une interface commune telle que:

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

Ensuite, donner des cours qui mettent en œuvre l'interface commune:

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) { 
     // ... 
    } 
} 

Votre mise en œuvre du EmptyTree impliqueront toujours un échec dans la recherche de l'élément (que ce soit en retournant null ou en lançant une exception), alors que votre implémentation de NonEmptyTree va soit retourner elle-même (si la clé de recherche fournie correspond) soit déléguer aux sous-arbres de gauche ou de droite. Parce que le sous-arbre gauche ou droit existera toujours (il s'agira d'un NonEmptyTree ou d'un EmptyTree), la classe "NonEmptyTree" peut simplement se référer à ses enfants via l'interface commune et compter sur le fait que le type d'exécution fera la bonne chose (il n'est donc pas nécessaire de faire un cast ou un contrôle de type des enfants dans la mise en œuvre de l'algorithme).

Le seul endroit où vous devez connaître le type d'exécution est lorsque vous construisez les enfants.