Scala中二叉树的尾递归最大深度方法 [英] Tail recursive maximum depth method of binary tree in Scala
本文介绍了Scala中二叉树的尾递归最大深度方法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我写了一个方法来计算二叉树的最大深度.
我想写一个尾递归方法.
我想过使用列表,但没有找到解决方案
这是我的非尾递归方法:
def 深度:Int = {def iter(f: FormulaWff): Int = f match {case Var(_) =>0case Not(e1) =>1 + 迭代(e1)情况 And(e1, e2) =>1 + Math.max(iter(e1), iter(e2))case Or(e1, e2) =>1 + Math.max(iter(e1), iter(e2))case 暗示(e1, e2) =>1 + Math.max(iter(e1), iter(e2))}迭代(这个)}
解决方案
试试
import scala.util.control.TailCalls.{TailRec, done, tailcall}特质公式Wff {定义深度:Int = {def iter(f: FormulaWff): TailRec[Int] = {def hlp(e1: FormulaWff, e2: FormulaWff): TailRec[Int] = for {x <- 尾调用(iter(e1))y <- 尾调用(iter(e2))} 产量 1 + Math.max(x, y)f 匹配 {case Var(_) =>完成(0)case Not(e1) =>为了 {x <- 尾调用(iter(e1))} 产量 1 + x情况 And(e1, e2) =>帮助(e1,e2)case Or(e1, e2) =>帮助(e1,e2)case 暗示(e1, e2) =>帮助(e1,e2)}}iter(this).result}}案例类 Var(s: String) 扩展了 FormulaWff案例类 Not(e: FormulaWff) 扩展了 FormulaWff案例类 And(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWffcase class Or(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWffcase class Implies(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWff
<小时>
直接解决
密封性状 FormulaWff最终案例类 Var(s: String) 扩展了 FormulaWff最终案例类 Not(e: FormulaWff) 扩展了 FormulaWff最终案例类 And(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWff最后一个案例类 Or(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWff最后一个案例类 Implies(e1: FormulaWff, e2: FormulaWff) 扩展了 FormulaWff密封性状 结果case 对象 NotExpanded 扩展结果case 对象扩展扩展结果最终案例类Calculated(value: Int) extends Result最终案例类框架(参数:FormulaWff,资源:结果)def depth(f: FormulaWff): Int = step1(List(Frame(f, NotExpanded))) 匹配{case Frame(arg,Calculated(res))::Nil =>资源}@tailrecdef step1(stack: List[Frame]): List[Frame] = {val x = step(stack, Nil)x 匹配 {case Frame(arg,Calculated(res))::Nil =>X案例_ =>步骤1(x)}}@tailrecdef step(stack: List[Frame], acc: List[Frame]): List[Frame] = {堆栈匹配{case Frame(_,Calculated(res1))::Frame(_,Calculated(res2))::Frame(And(e1,e2),Expanded)::frames=>step(frames, Frame(And(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)case Frame(_,Calculated(res1))::Frame(_,Calculated(res2))::Frame(Or(e1,e2),Expanded)::frames=>step(frames, Frame(Or(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)case Frame(_,Calculated(res1))::Frame(_,Calculated(res2))::Frame(Implies(e1,e2),Expanded)::frames=>step(frames, Frame(Implies(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)case Frame(_,Calculated(res1))::Frame(Not(e1),Expanded)::frames =>step(frames, Frame(Not(e1), Calculated(1 + res1)) :: acc)case Frame(Var(s), _) :: 帧 =>step(frames, Frame(Var(s),Calculated(0))::acc)case Frame(Not(e1), NotExpanded)::frames =>step(frames, Frame(Not(e1), Expanded) :: Frame(e1, NotExpanded) :: acc)case Frame(And(e1, e2), NotExpanded)::frames =>step(frames, Frame(And(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)case Frame(Or(e1, e2), NotExpanded) :: frames =>step(frames, Frame(Or(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)case Frame(Implies(e1, e2), NotExpanded)::frames =>step(frames, Frame(Implies(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)case Frame(arg, Expanded) :: 帧 =>step(frames, Frame(arg, Expanded) :: acc)case Frame(arg,Calculated(res))::frames =>step(frames, Frame(arg,Calculated(res))::acc)情况为零 =>反向}}
I wrote a method to calculate the maximum depth of a binary tree.
I would like to write a tail recursive method.
I thought of using lists, but I didn't find solutions
This is my method that is not tail recursive:
def depth: Int = {
def iter(f: FormulaWff): Int = f match {
case Var(_) => 0
case Not(e1) => 1 + iter(e1)
case And(e1, e2) => 1 + Math.max(iter(e1), iter(e2))
case Or(e1, e2) => 1 + Math.max(iter(e1), iter(e2))
case Implies(e1, e2) => 1 + Math.max(iter(e1), iter(e2))
}
iter(this)
}
解决方案
Try
import scala.util.control.TailCalls.{TailRec, done, tailcall}
trait FormulaWff {
def depth: Int = {
def iter(f: FormulaWff): TailRec[Int] = {
def hlp(e1: FormulaWff, e2: FormulaWff): TailRec[Int] = for {
x <- tailcall(iter(e1))
y <- tailcall(iter(e2))
} yield 1 + Math.max(x, y)
f match {
case Var(_) => done(0)
case Not(e1) => for {
x <- tailcall(iter(e1))
} yield 1 + x
case And(e1, e2) => hlp(e1, e2)
case Or(e1, e2) => hlp(e1, e2)
case Implies(e1, e2) => hlp(e1, e2)
}
}
iter(this).result
}
}
case class Var(s: String) extends FormulaWff
case class Not(e: FormulaWff) extends FormulaWff
case class And(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
case class Or(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
case class Implies(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
Direct solution
sealed trait FormulaWff
final case class Var(s: String) extends FormulaWff
final case class Not(e: FormulaWff) extends FormulaWff
final case class And(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
final case class Or(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
final case class Implies(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
sealed trait Result
case object NotExpanded extends Result
case object Expanded extends Result
final case class Calculated(value: Int) extends Result
final case class Frame(arg: FormulaWff, res: Result)
def depth(f: FormulaWff): Int = step1(List(Frame(f, NotExpanded))) match {
case Frame(arg, Calculated(res)) :: Nil => res
}
@tailrec
def step1(stack: List[Frame]): List[Frame] = {
val x = step(stack, Nil)
x match {
case Frame(arg, Calculated(res)) :: Nil => x
case _ => step1(x)
}
}
@tailrec
def step(stack: List[Frame], acc: List[Frame]): List[Frame] = {
stack match {
case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(And(e1, e2), Expanded) :: frames =>
step(frames, Frame(And(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(Or(e1, e2), Expanded) :: frames =>
step(frames, Frame(Or(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(Implies(e1, e2), Expanded) :: frames =>
step(frames, Frame(Implies(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
case Frame(_, Calculated(res1)) :: Frame(Not(e1), Expanded) :: frames =>
step(frames, Frame(Not(e1), Calculated(1 + res1)) :: acc)
case Frame(Var(s), _) :: frames =>
step(frames, Frame(Var(s), Calculated(0)) :: acc)
case Frame(Not(e1), NotExpanded) :: frames =>
step(frames, Frame(Not(e1), Expanded) :: Frame(e1, NotExpanded) :: acc)
case Frame(And(e1, e2), NotExpanded) :: frames =>
step(frames, Frame(And(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)
case Frame(Or(e1, e2), NotExpanded) :: frames =>
step(frames, Frame(Or(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)
case Frame(Implies(e1, e2), NotExpanded) :: frames =>
step(frames, Frame(Implies(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)
case Frame(arg, Expanded) :: frames => step(frames, Frame(arg, Expanded) :: acc)
case Frame(arg, Calculated(res)) :: frames => step(frames, Frame(arg, Calculated(res)) :: acc)
case Nil => acc.reverse
}
}
How to make tree mapping tail-recursive?
这篇关于Scala中二叉树的尾递归最大深度方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文