2-3-4树haskell

我已经给了一个任务来实现haskell中的2-3-4树的功能，问题是，我不确定如何定义2-3-4树。我一直在四处寻找，试图找到一个正确的方向指针，但那不太好。2-3-4树haskell

你能提出一个解决方案吗？

2011-11-29 TomSelleck

你是说，你不知道树是如何工作的（提示：搜索“2 3 4树”）？或者，你不知道如何在Haskell中实现它？ – Useless

解释维特根斯坦：关于树木可以说的一切可以在Haskell的几行中说。因此，如果难度在于您可以定义这样一棵树，但不在Haskell中，请说出您的想法，您将获得帮助。 – Ingo

是的我的意思是定义数据类型，对不起没有更清楚 – TomSelleck

要定义一个二叉树，你可以先写在纯英文的递归定义：

一个二叉树类型的值“X”是使用一个值的内部节点类型'x'以及具有类型'x'的值的两个子树或空叶节点。

然后很容易翻译成哈斯克尔：

data BinaryTree x = InternalNode x (BinaryTree x) (BinaryTree x) | LeafNode

2-3-4树从二叉树具有3种内部节点，而不是一个不同的，所以你需要更多的选择。

2011-11-29 17:07:04 nponeccop

数据树a =空|树（节点a）派生（显示） data Node a = Node2 a a | Node3 a a a | Node4 a a a a deriving（显示）我想出了这个到目前为止，你能告诉我是否正确的方向或什么？ – TomSelleck

你的问题有点含糊，因为不清楚你是否想要定义树结构本身或者在树上作用的函数。由于2-3-4树只是B-Tree，因此您可以直接使用Data.Tree并编写处理它的函数并强制执行您喜欢的约束。

如果你必须自己定义树数据类型，我建议为节点和节点的数据节点定义一个数据类型（2 | 3 | 4）。

2011-11-29 17:10:47 bbtrb

因为它是一个任务，我认为他应该自己定义数据类型和操作 – nponeccop

@nponeccop：听起来似乎合理，但如果他使用B-树，它的+/- 1行:) – bbtrb

感谢您的答复，我必须为树定义数据类型和函数。我确信一旦拥有数据类型，我就可以得到这些函数。 – TomSelleck

回答