在 Scala 中使用尾递归和匹配案例遍历二叉树

Question

我有一个案例 class 在 scala 中定义为

case class Node(key: String, value: String, var left: Node, var right: Node)

我正在尝试使用尾递归和匹配案例而不是循环和 if 语句来遍历它。我目前的遍历方法如下：

def find(key:String, tree:Node): Option[String] = {
    if(tree == null) {
        return None
    } else if (tree.key == key) {
        return Some(tree.value)
    }
    val checkLeft = find(key, tree.left)
    val checkRight = find(key, tree.right)
    if(checkLeft != None) {
        return checkLeft
    } else if(checkRight != None) {
        return checkRight
    }
    return None
}

我如何最好地创建与使用尾递归的案例的匹配？

我目前有：

key match {
    case tree.key => Some(tree.value)
    case _ => find(key, tree.left)
}

但显然这不会正确遍历我的整棵树。

Answer 1

case class Node(key: String, value: String, var left: Node, var right: Node)

object Tree
{
    def find(key: String, tree: Node): Option[String] =
    {
        @tailrec
        def find_with_accumulator(key: String, node_list: List[Node]): Option[String] =
        {
            node_list match
            {
                case Nil => None
                case Node(k, value, left, right) :: rest =>
                    if (k == key) Some(value)
                    // .flatten removes all the None and unwraps the Options
                    else
                    {
                        find_with_accumulator(key, List(left, right).filter(_ != null) ++ rest)
                    }
            }
        }

        find_with_accumulator(key, List(tree))
    }
}

改编自https://www.scala-lang.org/old/node/7984

我建议按如下方式更改树的表示形式：

sealed abstract class AbstractNode

case class EmptyNode() extends AbstractNode

case class Node(key: String, value: String, left: AbstractNode, right: AbstractNode) extends AbstractNode

object Tree
{
    def find(key: String, tree: AbstractNode): Option[String] =
    {
        @tailrec
        def find_with_accumulator(key: String, node_list: List[AbstractNode]): Option[String] =
        {
            node_list match
            {
                case Nil => None
                case EmptyNode() :: rest => find_with_accumulator(key, rest)
                case Node(k, value, left, right) :: rest =>
                    if (k == key) Some(value)
                    else find_with_accumulator(key, left :: right :: rest)
            }
        }

        find_with_accumulator(key, List(tree))
    }
}

在 Scala 中使用尾递归和匹配案例遍历二叉树

Use tail recursion and match cases to traverse a binary tree in Scala

scala

pattern-matching

binary-tree

binary-search-tree

tail-recursion