Functional Programming in Kotlin, Manning book - 二叉树结构

Question

我一直在完成本书中的练习。它写得很好，但移动速度非常快。到目前为止，我一直在跟上。

但是，我对二叉树的经验为零，所以我被困在了这个上。这是作业：

Write a function size that counts the number of nodes (leaves and branches) in a tree.

这是密封的树结构 class:

sealed class Tree<out A>
data class Leaf<A>(var value: A) : Tree<A>()
data class Branch<A>(val left: Tree<A>, val right: Tree<A>) : Tree<A>()

我不得不搜索有关二叉树的信息，并在 Kotlin 中找到了一个我能理解的示例。

但是该样本具有三态结构，而该练习具有双重状态：

class BinaryNode<Element>(
    val value: Element,
    var leftChild: BinaryNode<Element>? = null,
    var rightChild: BinaryNode<Element>? = null
) {

所以，我在使用密封 class 构建有效二叉树时遇到问题，我可以在上面测试练习解决方案，即：

fun <A> size(tree: Tree<A>): Int =
    when (tree) {
        is Leaf -> 1
        is Branch -> 1 + size(tree.left) + size(tree.right)
    }

解决方案看起来很合理，但不能完全弄清楚树的构造。

如有任何帮助，我们将不胜感激。

Answer 1

这是一个简单的例子：

fun main() {
    val tree = Branch(
        Branch(
            Leaf(1),
            Leaf(2)
        ),
        Branch(
            Leaf(3),
            Branch(
                Leaf(4),
                Leaf(5)
            )
        )
    )
    println(size(tree))
}

这会打印出 9，即 5 片叶子加上树枝。

Functional Programming in Kotlin, Manning book - 二叉树结构

Functional Programming in Kotlin, Manning book - binary tree structure

tree

binary-tree

functional-programming

kotlin