当前位置：文江博客话题详情

java 多态二叉搜索树

发布于 2024-08-27 15:17:40 字数 64 浏览 3 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

戏剧牡丹亭 2024-09-03 15:17:40

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

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”类可以通过公共接口简单地引用其子级，并依赖于运行时类型将执行正确操作的事实（因此在算法的实现中没有必要对子级进行任何转换或类型检查）。

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

Create a common interface such as:

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

Then provide classes that implement the common interface:

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

Your implementation for the EmptyTree will always indicate a failure in searching for the item (whether by returning null or by throwing an exception), while your implementation of NonEmptyTree will either return itself (if the provided search key matches) or delegate to the left or right subtrees. Because the left or right subtree will always exist (it will either be a NonEmptyTree or an EmptyTree), the "NonEmptyTree" class can simply refer to its children via the common interface and rely on the fact that the runtime type will do the right thing (thus it is not necessary to do any casting or type checking of the children in the implementation of the algorithm).

The only place where you need to know the runtime type is when you construct the children.

回复收藏 0 原文

~没有更多了~