使用Scala从Stream构建树

Question

我想构建一个从这个确切格式的随机高度文件中读取的树,

       1
      2 3
     4 5 6
    . . . .
   . . . . .

使用以下结构

case class Tree[+T](value : T, left :Option[Tree[T]], right : Option[Tree[T]])

我面临的挑战是,在构建树之前,我必须阅读最后一行,因为left它right是只读的.我尝试的方式是,

1. 读取第一行,创建一个值为(1)的节点,left并right设置为None.
2. 读取第二行,使用值(2)和(3)创建节点,left并right设置为None.这次,使用left= node(2)和right= node(3)创建新节点(1 ).
3. 阅读第三行,使用值(4),(5)和(6)创建节点,left并right设置为None.创建新节点(2)和节点(3)与节点(2) - >节点(4)和节点(5)和节点(3) - >节点(5)和节点(6),最后,节点(1) - >新节点(2)和节点(3)
4. 重复直到行结束.

最后,我应该有这种关系,

         1
        /  \
       2    3
      / \   / \
     4   5 5  6
    / \ /\ /\ / \
   .  .. . .. .  .

对我有什么好建议吗？谢谢

Answer 1

解决方案1

此解决方案以递归方式工作,并且需要已读取所有行.你总是在一排.如果有更多行,则Tree首先为这些行创建s.基本上它将首先Tree为叶子创建s.

当你拥有它们时,你知道第一个和第二个Tree形成新的Tree.第二个和第三个形成第二个新的Tree,依此类推.这是做什么的sliding.

作为滑动的一个例子: List(1,2,3,4).sliding(2) = List(List(1,2),List(2,3),List(3,4))

在这个解决方案中,我并没有注意效率.结果是Option[Tree].None如果没有值/没有线,则产生.它不处理字符串可能格式错误的情况.

case class Tree[+T](value : T, left :Option[Tree[T]], right : Option[Tree[T]])

def buildTree[T](lines: IndexedSeq[IndexedSeq[T]]) = {
  def recurse[T](lines: IndexedSeq[IndexedSeq[T]]): IndexedSeq[Tree[T]] = lines match {
    case line +: IndexedSeq() => line.map(Tree(_, None, None))
    case line +: rest => {
      val prevTrees = recurse(rest)
      (line, prevTrees.sliding(2).toIndexedSeq).zipped
      .map{case (v, IndexedSeq(left, right)) => Tree(v, Some(left), Some(right))}
    }
    case _ => IndexedSeq.empty
  }
  recurse(lines).headOption
}

例:

val input = """1
2 3
4 5 6""".stripMargin

val lines = input.lines.map(_.filterNot(_ == ' ').toIndexedSeq).toIndexedSeq
//Vector(Vector(1), Vector(2, 3), Vector(4, 5, 6))

val result = buildTree(lines)

这导致:

Some(Tree(1,Some(Tree(2,Some(Tree(4,None,None)),Some(Tree(5,None,None)))),Some(Tree(3,Some(Tree(5,None,None)),Some(Tree(6,None,None))))))

随机内幕(请忽略):我有点像zipped现在

解决方案2

这是一个像你描述的解决方案.它从上到下下降并在每次插入后更新树.它必须跟踪头部,因为当我们想要插入叶子时,我们必须修改所有父节点,这些节点不存储Tree.我不得不承认,所有这些都让事情变得非常混乱Option.

def buildTree2[T](lines: Iterator[IndexedSeq[T]]) = {
  @tailrec
  def loop(current: IndexedSeq[Tree[T]], head: Option[Tree[T]] = None): Option[Tree[T]] = {
    if(lines.hasNext) {
      val newTrees = lines.next.map(v => Option(Tree(v, None, None)))
      if(!current.isEmpty) {
        val h = (current, newTrees.sliding(2).toIndexedSeq).zipped.foldLeft(head.get) {
          case (nextHead, (parent, IndexedSeq(left, right))) => updateTree(nextHead, parent, Tree(parent.value, left, right))
        }
        loop(newTrees.flatten, Some(h))
      } else loop(newTrees.flatten, newTrees.head)
    } else head
  }

  def updateTree[T](head: Tree[T], target: Tree[T], replacement: Tree[T]): Tree[T] = {
    if(head eq target) {
      replacement
    } else head match {
      case Tree(v, Some(l), Some(r)) => Tree(v, Option(updateTree(l, target, replacement)), Option(updateTree(r, target, replacement)))
      case _ => head
    }
  }
  loop(IndexedSeq.empty)
}

现在我们可以将它与迭代器一起使用.

val lines = input.lines.map(_.filterNot(_ == ' ').toIndexedSeq)
buildTree2(lines)