# 泛函编程（8）－数据结构－Tree

上节介绍了泛函数据结构List及相关的泛函编程函数设计使用，还附带了少许多态类型（Polymorphic Type）及变形（Type Variance）的介绍。有关Polymorphism的详细介绍会放在typeclass讨论中。为了更多了解泛函数据结构（Functional Data Structure）,想在这个章节把另一个我们熟悉的数据结构-Tree做些简单介绍。

Tree的状态不是枝（Branch）就是叶（Leaf），这个很容易理解。那么就按照上节设计List那样设计Tree类型：

`1 trait Tree[+A]2 case class Leaf[A](value: A) extends Tree[A]3 case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]`

`1 val tree = Branch(Branch(Leaf(1),Leaf(2)),Branch(Branch(Leaf(10),Leaf(8)),Leaf(3)))2 //> tree : ch3.tree.Branch[Int] = Branch(Branch(Leaf(1),Leaf(2)),Branch(Branch(3 //| Leaf(10),Leaf(8)),Leaf(3)))`

`1 def size: Int = this match {2 case Leaf(_) => 13 case Branch(l,r) => 1 + l.size + r.size4 }`

`1 tree size //> res0: Int = 9`

`1 def countLeafs: Int = this match {2 case Leaf(_) => 13 case Branch(l,r) => 0 + l.size + r.size4  }5 def countBranches: Int = this match {6 case Leaf(_) => 07 case Branch(l,r) => 1 + l.size + r.size8  }9  `

`1 tree.countLeafs //> res1: Int = 82 tree.countBranches //> res2: Int = 9`

`1 def depth: Int = this match {2 case Leaf(_) => 03 case Branch(l,r) => 1 + (l.depth max r.depth)4 }`

`1 tree depth //> res1: Int = 3`

`1 def maxValue: Int = this match {2 case Leaf(a: Int) => a3 case Branch(l,r) => l.maxValue max r.maxValue4 }`

`1 tree maxValue //> res2: Int = 10`

`1 def fold[B](f: A => B)(g: (B,B) => B): B = this match {2 case Leaf(n) => f(n)3 case Branch(l,r) => g(l.fold(f)(g), r.fold(f)(g))4 }`

`1 def sizeByfold = fold(a => 1)(1 + _ + _)2 def maxValueByfold(l: Tree[Int]) = l.fold(a => a)((x,y) => 0 + (x max y))3 def depthByfold = fold(a => 0)((x,y) => 1 + (x max y))`

`1 tree sizeByfold //> res3: Int = 923 tree depthByfold //> res4: Int = 345 tree.maxValueByfold(tree) //> res5: Int = 10`

可能这个 tree.maxValueByfold(tree) 有点怪，但如果把函数实现放到 object Tree里然后import Tree._就可以了。

`1 def map[B](f: A => B): Tree[B] = this match {2 case Leaf(a) => Leaf(f(a))3 case Branch(l,r) => Branch(l.map(f),r.map(f))4  }5 def flatMap[B](f: A => Tree[B]): Tree[B] = this match {6 case Leaf(a) => f(a)7 case Branch(l,r) => Branch(l.flatMap(f), r.flatMap(f))8 }`

Top