没有为二叉树中的 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 方法中，当您尝试为 a 创建左节点时调用此方法节点。

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)
}

目前，我尝试了不同的实现，将 Ordering 添加到 abstract class 的通用类型或使 抽象 class 成为特征，但其中的 none 已经如我所愿。如果有人能解释为什么会出现此错误，我将不胜感激。

Answer 1

基本问题来自于没有 Ordering[Nothing] 这意味着 NullNode 不能被排序，但是 Node.value 类型需要。

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

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 { . . .

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

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

No implicit ordering defined for A in binary tree

binary-tree

scala

generic-programming

data-structures