时间戳

首页 > 解决方案 > Scala：从列表创建二叉树

scala - Scala：从列表创建二叉树

问题描述

我是 Scala 的完整初学者。所以我的问题可能很愚蠢，请耐心等待。我有一个二叉树结构的模板：

sealed trait Tree[T]
case class Leaf[T]() extends Tree[T]
case class Node[T](left: Tree[T], data :Int, right Tree[T]) extends Tree[T]

我想编写一个从列表创建二叉树的函数。第一个列表元素是根。分支左侧的所有数据都较小，分支右侧的所有数据都较大：

def listToTree[T](list: List[T]): Tree[T]

我不确定我写错了什么，但我的输出始终只是第一个List元素

def setElement(x: Int, tree: Tree[Int]): Tree[Int] = tree match {
    case Node(l, e, r) => Node(l, x, r)
    case Leaf() => new Node(Leaf(), x, Leaf()) 
}
def listToTree2[T](as: List[Int], tree: Tree[Int], x: Int): Tree[Int] = tree match
{
  case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
  case Node(left, e, right) => if(e < x) {
    right match {
      case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
      case Node(left2, e2, right2) => if( e < e2) listToTree2(as, right, x)
      else listToTree2(as, left, x)
    }
  } else if(e > x) { 
    left match {
      case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
      case Node(left3, e3, right3) => if( e < e3) listToTree2(as, right, x) else listToTree2(as, left, x)
    }
  } else {
    listToTree2(as.tail, tree, x)
  }
}


def listToTree[T](as: List[Int]): Tree[Int] =
{
  val tree = new Node(Leaf(), as.head, Leaf())
  listToTree2(as, tree, as.head)
}

所以最终正确的输出应该是这样的：


val list = List(3, 2, 4, 1)
assert(listToTree(list) == Branch(Branch(Branch(Leaf(),1,Leaf()),2,Leaf()))),3,Branch(Leaf(),4,Leaf()))

标签： scaladata-structuresbinary-tree

解决方案

你的代码中有一些东西似乎没有多大意义......但更重要的是，你写的东西对我来说是线性的，我很确定你不能在线性时间内构建 BST （如果可以的话，你也可以按线性时间排序，这会很酷）。因此，看起来与其尝试调试此代码，不如将其扔掉，并重新考虑整个方法。

不幸的是，不可变结构并不能使非线性事物的实现变得特别容易。您可以在这里尝试几种方法。特别是partition从快速排序中借用了这个想法：

def makeTree(data: List[Int]): Tree[Int] = data match {
   case Nil => Leaf()
   case head :: tail => 
      val (left, right) = tail.partition(_ < head)
      Branch(makeTree(left), head, makeTree(right.filterNot(_ == head)))
}

推荐阅读