haskell - 这个二叉树代码如何表示一棵树？

Question

我正在阅读大学 Haskell 考试过去的试卷，遇到一个涉及树的问题，其中树类型是这样实现的:

data Tree a = Lf a                  -- leaf
            | Tree a :+: Tree a     -- branch

然后，它继续概述可与各种函数一起使用的示例树，例如:

((Lf 1 :+: Lf 2) :+: (Lf 3 :+: Lf 4))

我对这段代码的困惑是它如何在没有根元素概念的情况下表示一棵树。我的直觉表明这里代表的树看起来像这样:

  / \
/ \ / \
1 2 3 4

但是这样的树不会有根元素，只有叶子，这对我来说肯定是错误的。这段代码实际上是如何表达一棵树的？

Answer 1

这是一棵树，数据仅存储在叶子中。不要求树的内部节点有数据，尽管许多算法当然只能对内部节点有数据的树进行操作(例如 BST 搜索)。

你可能会问这样的结构在什么情况下有用。考虑霍夫曼解码，其中内部节点不需要数据。您只需沿着树向下遍历，在 0 上向左移动，在 1 上向右移动，直到到达叶节点，此时您已经解码了一个字符。