关于scala:scala二叉树深度优先遍历

简化定义 Scala Tree 构造，蕴含两个局部：Branch 和 Tree。为了简化数据结构，Branch 只蕴含 Tree 类型的左节点和右节点，Leaf 蕴含具体 Value

sealed trait Tree[+A]

case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

树的遍历右两种形式：

深度优先
广度优先

这里用 DFS 实现，深度优先搜寻属于图算法的一种，英文缩写为 DFS 即 Depth First Search，其过程简要来说是对每一个可能的分支门路深刻到不能再深刻为止，而且每个节点只能拜访一次。

具体搜寻程序能够参考附图

搜寻根节点左子树
搜寻以后树的左子树
搜寻以后树的左子树
返回父节点，搜寻父节点右子树
搜寻以后树的左子树
返回父节点，搜寻父节点右子树
返回父节点，返回父节点，返回父节点，搜寻右子树
….

咱们从一道题来相熟 Scala 遍历操作,求 Scala 树中节点总数
依照 DFS 思维实现代码如下

 def countNodes[A](tree: Tree[A]): Int = {def go[A](tree: Tree[A], sum: Int): Int = tree match {case Leaf(v) => sum + 1       // 叶子节点 sum+1
      case Branch(left, right) => sum + 1 + go(left, 0) + go(right, 0)  // 分支节点 sum = sum + 1 + 左子树节点总数 + 右子树节点总数
      case _ => 0
    }
    go(tree, 0) // 递归
  }

联合【Scala 笔记——道】Scala List HOF foldLeft / foldRight 中讲到的 List fold 思维

咱们将 countNode 办法的遍历进行抽象化
，首先一个函数最重要的就是 输出 / 输入 ，参考 List fold，不难理解对 Tree 的函数操作必然是将 Tree[A] 转化为 [B]，咱们这里实现的简化树模型中，Value 的具体存储都在叶子节点中，因而

 def deepFirstSearch[A, B](tree: Tree[A])(f: A => B)...  = tree match {case Leaf(value) => f(value)
      ...
  }

其次，将 DFS 搜寻的过程进行形象。对每一个枝点，首先搜寻枝点的左节点，失去左节点执行后果当前，再搜寻右节点，失去右节点执行后果当前，执行对左右子树函数后果的函数操作，因而

 def deepFirstSearch[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B) : B  = tree match {case Leaf(value) => f(value)
      case Branch(l, r) => g(deepFirstSearch(l), deepFirstSearch(r) )
  }

通过几个小例子来实际 deepFirstSearch

获取 Tree[Int]中最大值

def maximum(tree: Tree[Int]): Int =
    deepFirstSearch(tree)(l => l)(_ max _)

求树的最大深度

 def depth[A](tree: Tree[A]): Int =
    deepFirstSearch(tree)(_ => 1)(_.max(_) + 1)

MAP 函数将 A 转化为 B

def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = {deepFirstSearch(tree)(x => (Leaf(f(x)): Tree[B]))((a, b) => Branch(a, b))

测试如下

 def main(args: Array[String]): Unit = {

    val tree = Branch(
                  Branch(
                    Branch
                      (Leaf(1),
                        Branch(Leaf(7),
                          Branch(Leaf(8),
                            Leaf(9)
                          ))),
                    Branch(Leaf(34), Leaf(4))),
                  Branch(Leaf(5), Leaf(6)))

    println("Max value :" + maximum(tree))

    println("Depth :" + depth(tree))

    println("Map :" + map(tree)(x => if(x%2 == 0) Branch(Leaf(1), Leaf(2)) else x))
  }

后果如下

Max value :34
Depth :6
Map :Branch(Branch(Branch(Leaf(1),Branch(Leaf(7),Branch(Leaf(Branch(Leaf(1),Leaf(2))),Leaf(9)))),Branch(Leaf(Branch(Leaf(1),Leaf(2))),Leaf(Branch(Leaf(1),Leaf(2))))),Branch(Leaf(5),Leaf(Branch(Leaf(1),Leaf(2)))))

关于scala:scala二叉树深度优先遍历

Tree 定义

深度优先遍历 DFS

应用