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」類可以通過公共接口簡單地引用其子級，並依賴於運行時類型將做正確事情的事實（因此在執行該算法時不需要進行任何鑄造或類型檢查）。

您需要知道運行時類型的唯一地方是在構建子代時。