以功能方式遍历树

Question

我已经在Scala中实现了一个基本的可变树，我想以一种功能性的方式遍历它以便搜索元素，但是我不知道如何实现它。我还希望该算法尽可能地尾部递归。

树是具有值和也是树的叶子列表的结构。

任何帮助，将不胜感激。

这是我的代码（专注于getOpt方法）：

package main

import scala.collection.mutable.ListBuffer

sealed trait Tree[Node] {

  val node: Node

  val parent: Option[Tree[Node]]

  val children: ListBuffer[Tree[Node]]

  def add(n: Node): Tree[Node]

  def size: Int

  def getOpt(p: (Node) => Boolean): Option[Tree[Node]]

  override def toString = {
    s"""[$node${if (children.isEmpty) "" else s", Children: $children"}]"""
  }
}

case class ConcreteTree(override val node: Int) extends Tree[Int] {

  override val children = ListBuffer[Tree[Int]]()

  override val parent: Option[Tree[Int]] = None

  override def add(n: Int): ConcreteTree = {
    val newNode = new ConcreteTree(n) {override val parent: Option[Tree[Int]] = Some(this)}
    children += newNode
    newNode
  }

  override def size: Int = {
    def _size(t: Tree[Int]): Int = {
      1 + t.children.foldLeft(0)((sum, tree) => sum + _size(tree))
    }
    _size(this)
  }

  // This method is not correct
  override def getOpt(p: (Int) => Boolean): Option[Tree[Int]] = {
    def _getOpt(tree: Tree[Int], p: (Int) => Boolean): Option[Tree[Int]] = {
      tree.children.map {
        t =>
          if(p(t.node)) Some(t) else t.children.map(_getOpt(_, p))
      }
    }
  }
}

object Main {

  def main(args: Array[String]) {
    val tree1 = ConcreteTree(1)
    val tree2 = tree1.add(2)
    val tree3 = tree1.add(3)

    println(tree1.getOpt(_ == 2))
  }
}

@doertsch答案是我目前拥有的最佳方法。

Answer 1

实际上，我会寻求一些更灵活的方法，并实现一个泛型函数来生成扁平化树的惰性流，那么以后的许多工作将变得更加容易。像这样：

def traverse[Node](tree: Tree[Node]): Stream[Tree[Node]] = 
  tree #:: (tree.children map traverse).fold(Stream.Empty)(_ ++ _)

然后，您getOpt可以简化为：

override def getOpt(p: (Int) => Boolean): Option[Tree[Int]] =
  traverse(tree) find {x => p(x.node)}

进一步简化，如果您只是对没有Tree结构的数据感兴趣，则可以获取节点流，从而获得：

def nodes[Node](tree: Tree[Node]): Stream[Node] = traverse(tree) map (_.node)

def getNode(p: (Int) => Boolean): Option[Int] = nodes(tree) find p

这就为非常简洁可读的代码像其他的可能性nodes(tree) filter (_ > 3)，nodes(tree).sum，nodes(tree) contains 12，和类似的表述。