这段二叉树代码如何表示一棵树？

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

但是这样的树将没有根元素，只有叶子节点，这对我来说显然是错误的。如何在这段代码中实际表示树形结构？

- Paul Clavier

Answer 1

这是一棵仅在叶子节点存储数据的树。虽然许多算法只能处理存在内部节点数据的树（例如BST搜索），但并不要求树必须在内部节点中存储数据。

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

- amalloy

---

所以我的直觉是正确的，谢谢你澄清了这个问题！ - Paul Clavier