如何在Scala中正确实现多态函数式Tree数据结构？

你的代码核心问题是case object Void无法继承泛型特质Tree[A]——单例对象不能携带类型参数，无法为每个A生成对应实例。Scala里的标准解决思路是利用协变特质结合Nothing类型，这也是标准库中类似空结构（比如Nil）的实现范式：

1. 给特质Tree添加协变标注+A，让Tree[Nothing]可被视为所有Tree[A]的子类型
2. 让Void继承Tree[Nothing]，这样它就能被当作任意类型的空树使用

修改后的代码如下：

trait Tree[+A]

case object Void extends Tree[Nothing]
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]

使用时Void可直接赋值给任意Tree[A]类型的变量：

val emptyIntTree: Tree[Int] = Void
val emptyStringTree: Tree[String] = Void

如果想要更清晰的语义，还可以给Tree添加伴生对象方法封装空树：

trait Tree[+A]

case object Void extends Tree[Nothing]
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]

object Tree {
  def empty[A]: Tree[A] = Void
}

// 使用示例
val emptyIntTree: Tree[Int] = Tree.empty[Int]

如果不想使用协变，也可以将Void定义为泛型case class，但这种方式每次创建空树都要显式指定类型，不如协变方案简洁：

trait Tree[A]

case class Void[A]() extends Tree[A]
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]

// 使用示例
val emptyIntTree: Tree[Int] = Void[Int]()

内容的提问来源于stack exchange，提问作者Matei