scala - 使用 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。这次，创建了一个新节点 (1)，其中 left = node(2) 和 right = node(3)。
3. 阅读第三行，创建值为 (4)、(5) 和 (6) 的节点，并将 left 和 right 设置为 None。使用 node(2) -> node(4) and node(5) and node(3) -> node(5) and node(6) 创建新的 node(2) 和 node(3)，最后是 node(1) -> 新节点(2)和节点(3)
4. 重复直到行尾。

说到底，我应该有这段感情，

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

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

Answer 1

解决方案一

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

当你拥有它们时，你知道第一和第二 Tree 形成了新的 Tree。第二个和第三个组成第二个新的Tree等等。这就是滑动的作用。

以滑动为例: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)

结果是:

一些(树(1，一些(树(2，一些(树(4，无，无))，一些(树(5，无，无)))，一些(树(3，一些(树(5，无，无))，一些(树(6，无，无))))))

随机内部人士(请忽略):我现在有点喜欢zipped

方案二

这是您描述的解决方案。它从上到下向下并在每次插入后更新树。但它必须跟踪头部，因为当我们想要插入叶子时，我们必须修改所有父节点，而该引用未存储在 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)