如何在Scala中展平树木？

Question

编写flatten(lol: List[List[T]]): List[T]列表列表到新列表很容易。其他“扁平”集合（例如Set）似乎也提供flatten了。

现在，我想知道是否可以定义flattenfor Tree[T]（定义为T和的列表Tree[T]）。

Answer 1

这不是完美的，仅作为示例。您需要做的就是以深度优先或宽度优先的方式遍历一棵树并收集结果。与flatten清单几乎相同。

1）定义一个树结构（我知道，这不是最好的方法：））：

scala> case class Node[T](value: T, left: Option[Node[T]] = None,
     |  right: Option[Node[T]] = None)
defined class Node

2）创建一棵小树：

scala> val tree = Node(13,
     |   Some(Node(8,
     |     Some(Node(1)), Some(Node(11)))), 
     |   Some(Node(17,
     |     Some(Node(15)), Some(Node(25))))
     | )
tree: Node[Int] = Node(13,Some(Node(8,Some(Node(1,None,None)),Some(Node(11,None,None)))),Some(Node(17,Some(Node(15,None,None)),Some(Node(25,None,None)))))

3）实现可以遍历树的功能：

scala> def observe[T](node: Node[T], f: Node[T] => Unit): Unit = {
     |   f(node)
     |   node.left foreach { observe(_, f) }
     |   node.right foreach { observe(_, f) }
     | }
observe: [T](node: Node[T], f: Node[T] => Unit)Unit

4）使用它来定义一个打印所有值的函数：

scala> def printall = observe(tree, (n: Node[_]) => println(n.value))
printall: Unit

5）最后，定义该flatten函数：

scala> def flatten[T](node: Node[T]): List[T] = {
     |   def flatten[T](node: Option[Node[T]]): List[T] =
     |     node match {
     |       case Some(n) =>
     |         n.value :: flatten(n.left) ::: flatten(n.right)
     |       case None => Nil
     |     }
     |  
     |  flatten(Some(node))
     | }
flatten: [T](node: Node[T])List[T]

6）让我们测试一下。首先打印所有元素：

scala> printall
13
8
1
11
17
15
25

7）运行flatten：

scala> flatten(tree)
res1: List[Int] = List(13, 8, 1, 11, 17, 15, 25)

这是一种诸如树遍历的通用树算法。我让它返回Ts而不是Nodes，并根据需要进行更改。