我正在阅读大学 Haskell 考试的过去论文，并遇到了一个涉及树的问题，其中树类型是这样实现的:
data Tree a = Lf a -- leaf
| Tree a :+: Tree a -- branch
然后继续概述可用于各种功能的示例树，例如:
((Lf 1 :+: Lf 2) :+: (Lf 3 :+: Lf 4))
我对这段代码的困惑在于它如何在没有根元素概念的情况下表示一棵树。我的直觉会建议这里表示的树看起来像这样:
/ \
/ \ / \
1 2 3 4
但是这样的树没有根元素，只有叶子，这在我看来肯定是错误的。在这段代码中，树实际上是如何表达的？
最佳答案
它是一棵树，数据仅存储在叶子中。不要求树的内部节点有数据，尽管当然许多算法只能对内部节点有数据的树进行操作(例如 BST 搜索)。
您可能会问这种结构在什么情况下有用。考虑霍夫曼解码，其中内部节点不需要数据。您只需沿着树向下遍历，在 0 处向左移动，在 1 处向右移动，直到到达叶节点，此时您已经解码了一个字符。
关于haskell - 这个二叉树代码如何表示一棵树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59039754/