0

对于一个辅助项目，我想要一种简单的方法来从排序的流中生成持久的二叉搜索树。经过一些粗略的搜索后，我只能找到涉及存储排序数组的技术描述，您可以在其中通过索引访问任何元素。我最终写了一些有用的东西，但我认为这是一个很好的领域，一个规范的例子可能记录在某个地方（并且可能有一个名字）。

为了清楚起见，我制作的 make shift 代码被包含在内。（也很短）

object TreeFromStream {
  sealed trait ImmutableTree[T] {
    def height: Int
  }
  case class ImmutableTreeNode[T](
    value: T,
    left: ImmutableTree[T],
    right: ImmutableTree[T]
  ) extends ImmutableTree[T] {
    lazy val height = left.height + 1
  }
  case class NilTree[T]() extends ImmutableTree[T] {
    def height = 0
  }

  @tailrec
  def treeFromStream[T](
    stream: Stream[T],
    tree: ImmutableTree[T] = NilTree[T](),
    ancestors: List[ImmutableTreeNode[T]] = Nil
  ): ImmutableTree[T] = {
    (stream, ancestors) match {
      case (Stream.Empty, _) =>
        ancestors.foldLeft(tree) { case(right, root) => root.copy(right=right) }
      case (_, ancestor :: nextAncestors) if ancestor.left.height == tree.height =>
        treeFromStream(stream, ancestor.copy(right=tree), nextAncestors)
      case (next #:: rest, _) => 
        treeFromStream(
          rest, NilTree(),
          ImmutableTreeNode(next, tree, NilTree()) :: ancestors
        )
    }
  }
}
4

1 回答 1

-1

要创建一个平衡树，我猜你想这样做，你需要至少访问每个节点一次。首先，将所有节点收集到一个缓冲区中，然后将缓冲区递归转换为树：

  def tfs[T](stream: Stream[T]): ImmutableTree[T] = {
    val ss = scala.collection.mutable.ArrayBuffer.empty[T]
    def treeFromSubsequence(start: Int, end: Int): ImmutableTree[T] =
      if (end == start) NilTree()
      else if (end - start == 1) ImmutableTreeNode(ss(start), NilTree(), NilTree())
      else {
        val mid = (end - start) / 2
        ImmutableTreeNode(ss(mid), treeFromSubsequence(start, mid), treeFromSubsequence(mid + 1, end))
      }
    stream.foreach { x => ss += x }
    treeFromSubsequence(0, ss.length)
  }

它会准确地访问每个值两次，一次是收集它，一次是把它放入树的值字段中。

于 2018-06-19T21:58:46.177 回答