scala 计算树中的节点数

Question

我有一棵树定义为

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]

我想要一个计算树中节点数的函数和一个计算叶子数的函数

（我写了一个函数来计算叶子的数量，但我对我使用的方法不满意。我想要一个更多的 "functional" 实现）。

val t1 = Branch(
             Branch(
               Leaf(12),
               Branch(
                 Leaf(3),
                 Leaf(4))),
             Leaf(8))                             //> t1  : trees.Branch[Int] = Branch(Branch(Leaf(12),Branch(Leaf(3),Leaf(4))),Le
                                                  //| af(8))

def n_nodes(t:Tree[Int]):Int = {
    var s = 0
    def n_nodesAcc(t:Tree[Int]):Unit = {

    t match {
        case Branch(left, right) =>{
            n_nodesAcc(left)
            n_nodesAcc(right )
            }
        case Leaf(v) => {s = s+ 1}
    }


}

n_nodesAcc(t)
s
}                                                 //> n_nodes: (t: trees.Tree[Int])Int

n_nodes(t1)                                       //> res0: Int = 4

（这是一个练习）

Answer 1

你可以写一个递归的方法来计算树叶的数量：

def countLeaves[A](tree: Tree[A]): Int = tree match {
    case l:Leaf[A] => 1
    case b:Branch[A] => countLeaves(b.left) + countLeaves(b.right)
}

或者统计所有的节点：

def countNodes[A](tree: Tree[A]): Int = tree match {
    case l:Leaf[A] => 1
    case b:Branch[A] => 1 + countLeaves(b.left) + countLeaves(b.right)
}

你也可以写一个类似的方法来获取所有的叶子，以后你可以更灵活地做不同的功能：

def getLeaves[A](tree: Tree[A]): Seq[Leaf[A]] = tree match {
    case l:Leaf[A] => Seq(l)
    case b:Branch[A] => getLeaves(b.left) ++ getLeaves(b.right)
}

然后用getLeaves(t1).length计数。或者类似的，获取所有的节点：

def getNodes[A](tree: Tree[A]): Seq[Tree[A]] = tree match {
    case l:Leaf[A] => Seq(l)
    case b:Branch[A] => Seq(b) ++ getNodes(b.left) ++ getNodes(b.right)
}

scala 计算树中的节点数

scala count number of nodes in a tree

tree

scala