使用 Scala 的二叉树

Question

class MyBst {
  def createTree(list:List[Int]): Node={
    require(list.nonEmpty)
      val nodes = list.map(element => Node(None, element, None))
      val root = nodes.head
      def create(node:List[Node], tree:Node):Node=
        nodes match{
          case head::tail => create(tail,insert(tree,head))
          case Nil => tree
        }
      create(nodes.tail,root)
  }
  def insert(tree:Node,elem:Node):Node = {
    if(tree.data >= elem.data)
      if(tree.left.isDefined)
        tree.copy(left = Some(insert(tree.left.get,elem)))
       else
        tree.copy(left = Some(elem))
    else
      if(tree.right.isDefined)
        tree.copy(right = Some(insert(tree.right.get,elem)))
      else
        tree.copy(right=Some(elem))
  }

}
case class Node(left:Option[Node], data:Int, right:Option[Node])

我正在尝试使用 Scala 创建一棵树。但这是行不通的。它显示堆栈溢出错误。

[info] java.lang.WhosebugError:

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

Answer 1

在您的 create 函数中，您在 nodes 而不是 node 上进行模式匹配。一旦你解决了这个问题，你可能会意识到 create Tree 并不是 return 树的顶部

使用 Scala 的二叉树

Binary Tree using Scala

binary-tree

scala