以函数方式遍历树 [英] Traverse tree in a functional way

问题描述

我已经在 Scala 中实现了一个基本的可变树，我想以函数方式遍历它以搜索元素，但我不知道如何实现它.如果可能，我还希望算法是尾递归的.

I've implemented a basic mutable tree in Scala and I want to traverse it in a functional way in order to search for an element, but I don't know how to implement it. I want also the algorithm to be tail recursive if possible.

树是一种结构，具有值和也是树的叶子列表.

The tree is a structure with a value and a list of leafs that are also trees.

任何帮助将不胜感激.

这是我拥有的代码(专注于 getOpt 方法):

This is the code that I have (focus on getOpt method):

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 的回答是我目前最好的方法.

@doertsch answer is the best approach that I have at the moment.

推荐答案

我实际上会寻求更灵活的方法并实现一个通用函数来生成扁平树的惰性流，然后你以后的很多工作就会变得很多更轻松.像这样:

I would actually go for something more flexible and implement a generic function to produce a lazy stream of your flattened tree, then a lot of your later work will become much easier. Something like this:

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

然后你的 getOpt 减少到这个:

Then your getOpt reduces to this:

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

进一步简化，如果你只对没有 Tree 结构的数据感兴趣，你可以得到一个节点流，给你:

Simplifying even further, if you're just interested in the data without the Tree structure, you can just get a stream of nodes, giving you:

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) 包含 12 个，以及类似的表达式.

This opens other possibilities for very concise and readable code like nodes(tree) filter (_ > 3), nodes(tree).sum, nodes(tree) contains 12, and similar expressions.

这篇关于以函数方式遍历树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！