OCaml：树函数

是否有任何用于处理树的模块或函数？我有一个类型，看起来像这样：OCaml：树函数

type t = 
     Leaf of string (* todo: replace with 'a *) 
     | Node of string * t list

，我努力做的插入，删除子树等

我用谷歌，但不能发现任何东西。

来源

2009-09-25 Nick Heiner

阅读模块的实现在OCaml标准库的源文件中设置。它们是用二叉树实现的，只比你更复杂一些。

（我建议你开始与二叉树而不是孩子的名单，你似乎已经定义）

来源

2009-09-25 02:27:03

是的，但我使用这些树来做句子的语法，所以我不能只是在那里扔价值。他们需要维护秩序，我希望通过恰当地创建树来建立这个顺序，但我想我可以使用一个包含数字和单词本身的包装类型... – 2009-09-25 02:31:14

你*可以*建立顺序正确创建树。实际上，模块集依次维护树的元素（最左边的后代中的最低元素），所以我仍然认为这是一个很好的灵感来源。 – 2009-09-25 02:35:26

其实这取决于你希望你的树的工作方式，例如，如果有订单元素之间等等。

否则，您可以使用树上的已知算法，如果您有一个想法如何以其他语言C或Java为例，我可以帮助将其转换为OCAML。

来源

2009-09-28 09:56:00 0xFF

在过去，我用。这不是一个简单的lib使用，但如果你需要插入节点和改变路径，这可能的伎俩，我从来没有在b-tree上下文中使用它...

并从语言的文档：

的变量类型的最常见的用法是描述递归数据结构。例如，考虑类型的二进制树的：

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;; 
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree

该定义读取如下：含类型的值的二进制树“一个（任意类型）或者是空的，或者是包含一个类型为'a'的值的节点以及也包含类型'a，即两个'树的值的两个子树。

对二叉树的操作是自然地表示为递归功能遵循相同的结构作为类型定义本身。对于例如，这里有功能进行查找，插入有序二叉树（元素增加，从左至右）：

#let rec member x btree = 
    match btree with 
    Empty -> false 
    | Node(y, left, right) -> 
     if x = y then true else 
     if x < y then member x left else member x right;; 
val member : 'a -> 'a btree -> bool = <fun> 

#let rec insert x btree = 
    match btree with 
    Empty -> Node(x, Empty, Empty) 
    | Node(y, left, right) -> 
     if x <= y then Node(y, insert x left, right) 
       else Node(y, left, insert x right);; 
val insert : 'a -> 'a btree -> 'a btree = <fun>

希望这有助于

来源

2009-09-29 20:04:09 LB40

是否必须在某处定义节点？我看到你在插入Node中使用某种构造函数，它是如何工作的，它在哪里实现？或者Node（x，left，right）只是模式匹配？如果是这样，你能解释一下这个语法吗？谢谢，你的帖子非常有帮助。 – 2012-09-29 17:18:24

除了@ LB40的答案在这里删除：http://geck1.blogspot.com/2014/02/ocaml-review-day-4-binary-tree-ops.html – BRS 2014-02-11 08:54:30

有一个Ptree数据类型由Matt我想，麦克唐纳能够做到你所需要的。

来源

2011-06-02 09:10:11 Gaius

回答

相关问题