Используйте хвостовую рекурсию и сопоставьте регистры, чтобы просмотреть двоичное дерево в Scala - PullRequest
Новая
       68

Используйте хвостовую рекурсию и сопоставьте регистры, чтобы просмотреть двоичное дерево в Scala

0 голосов
/ 17 сентября 2018

У меня есть класс case, определенный в 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)
}

но, очевидно, это не будет правильно проходить через все мое дерево.

1 Ответ

0 голосов
/ 17 сентября 2018 
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))
    }
}
...