二叉树中没有为 A 定义隐式排序

Question

我正在尝试在 Scala 中开发一个二叉树结构，但我有一个错误说：

Error:(15, 54) No implicit Ordering defined for A.
override def add[A](new_value: A): BinaryTree[A] = new Node(NullNode,new_value,NullNode)

谁能解释我如何解决它？这是代码，问题出在NullNode对象的add方法中，当您尝试为Node创建 left 时会调用此方法。

sealed abstract class BinaryTree[+A] {
def isEmpty: Boolean
def isValid: Boolean
def add[B >: A](new_value: B): BinaryTree[A]
def isLeaf: Boolean
def length: Int
}
case object NullNode extends BinaryTree[Nothing] {
override def isEmpty: Boolean = true
override def isValid: Boolean = true
override def isLeaf: Boolean = false
override def add[A](new_value: A): BinaryTree[A] = new Node(NullNode,new_value,NullNode)
override def length: Int = 0
}
case class Node[A] (
var left  : BinaryTree[A],
var value : A,
var rigth : BinaryTree[A] )
( implicit ord: Ordering[A] ) extends BinaryTree[A] {
override def isEmpty: Boolean = false
override def isValid: Boolean = {
import ord._
def isValidWith (f: A => Boolean, t: BinaryTree[A]): Boolean = t match {
case NullNode => true
case Node(_,valueNode,_) => f(valueNode) && t.isValid
}
isValidWith(value < _, left) && isValidWith(value > _, rigth)
}
override def isLeaf: Boolean = left.isEmpty && rigth.isEmpty
override def add[B >: A](new_value: B): BinaryTree[A] = {
import ord._
def travel (t: BinaryTree[A]): BinaryTree[A] = t match {
case NullNode => t.add(new_value)
case Node (left,nodeValor,rigth) => {
if (new_value > nodeValor) new Node(travel(left),nodeValor,rigth)
else if (new_value < nodeValor) new Node(left,nodeValor, travel(rigth))
else throw new Exception("Valor ya introducido")
}
}
travel(this)
}
override def length: Int = {
def travel (t: BinaryTree[A]): Int = t match {
case NullNode => t.length
case Node(left,_,rigth) => left.length + rigth.length + 1
}
travel(this)
}
}
object BinaryTree {
def apply[A] (value: A)(implicit ord: Ordering[A]): BinaryTree[A] = new Node(NullNode,value,NullNode)
}

目前，我已经尝试了不同的实现，将Sort添加到抽象类的泛型类型或使抽象类成为特征，但这些都没有像我想要的那样工作。如果有人能解释为什么会出现此错误，我将不胜感激。

Answer 1

基本问题来自没有Ordering[Nothing]这意味着NullNode无法订购，但需要Node.value类型。

我通过向每个add()方法引用添加Ordering并调整value类型与left/right节点类型之间的关系来编译它。

sealed abstract class BinaryTree[+A] {
def isEmpty: Boolean
def isValid: Boolean
def add[B >: A :Ordering](new_value: B): BinaryTree[B]
. . .

。

case object NullNode extends BinaryTree[Nothing] {
override def isEmpty: Boolean = true
override def isValid: Boolean = true
override def isLeaf: Boolean = false
override def add[A:Ordering](new_value: A): BinaryTree[A] =
Node(NullNode, new_value, NullNode)
. . .

。

case class Node[A,C<:A](left  : BinaryTree[C]
,value : A
,rigth : BinaryTree[C]
)(implicit ord: Ordering[A]) extends BinaryTree[A] { . . .

。

override def add[B >: A :Ordering](new_value: B): BinaryTree[B] = {
import ord._
def travel(t: BinaryTree[A]): BinaryTree[B] = t match { . . .

代码还有其他问题和问题，但至少可以编译。