haskell - 以下某些树数据类型在计算机科学中使用的名称是什么？

Question

有时我在 Haskell 中使用不同类型的树，但我不知道它们叫什么，也不知道在哪里可以获取有关使用它们的算法或它们的类实例的更多信息，甚至不知道一些预先存在的代码或库黑客攻击。

示例:

标签位于叶子或 Twig 上的二叉树:

data BinTree1 a = Leaf | 
                  Branch {label :: a, leftChild :: BinTree1 a, rightChild :: BinTree1 a}

data BinTree2 a = Leaf {label :: a} | 
                  Branch {leftChild :: BinTree2 a, rightChild :: BinTree2 a}

类似地，每个子节点都有标签或所有子节点都有通用标签的树:

data Tree1 a = Branch {label :: a, children :: [Tree1 a]}

data Tree2 a = Branch {labelledChildren :: [(a, Tree2 a)]}

有时我开始使用 Tree2 ，在开发过程中不知何故它被重构为 Tree1 ，这看起来更容易处理，但我从来没有考虑太多关于它。这里有某种二元性吗？

此外，如果您可以发布一些您认为有用的其他不同种类的树，请这样做。

总之:你能告诉我的关于这些树的一切都会有用! :)

谢谢。

编辑:

澄清:这不是家庭作业。只是我通常最终会使用这些数据类型并创建实例(Functor、Monad 等)，也许如果我更新它们的名称，我会找到包含已实现内容和更多理论信息的库。

通常，当 Hackage 上的库名称中包含 Tree 时，它​​会实现 BinTree2 或仅在叶子上带有标签的非二叉树的某些版本，所以在我看来，Tree2 和 BinTree2 可能有其他名称或标识符.

而且我觉得可能存在某种对偶性或同构性，或者通过某种转换将使用 Tree1 的代码转换为使用 Tree2 的代码的方法。有没有？也许这只是一个印象。

Answer 1

我听过的名字:

• BinTree1 是 binary tree
• BinTree2 不知道名称，但您可以使用这样的树来表示无前缀代码，例如霍夫曼编码
• Tree1 是 Rose tree
• Tree2 与 [Tree1] 同构(Tree1 的森林)，或者以另一种方式查看它是 Tree1 没有根标签。