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

Tree 定义

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

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

1. 搜寻根节点 左子树
2. 搜寻以后树的左子树
3. 搜寻以后树的左子树
4. 返回父节点，搜寻父节点 右子树
5. 搜寻以后树的左子树
6. 返回父节点，搜寻父节点 右子树
7. 返回父节点，返回父节点，返回父节点，搜寻右子树
8. ….

咱们从一道题来相熟 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)))))