OCaml：樹函數

Question

是否有任何用於處理樹的模塊或函數？我有一個類型，看起來像這樣：

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

，我努力做的插入，刪除子樹等

我用谷歌，但不能發現任何東西。

Answer 1

閱讀模塊的實現在OCaml標準庫的源文件中設置。 它們是用二叉樹實現的，只比你更復雜一些。

（我建議你開始與二叉樹而不是孩子的名單，你似乎已經定義）

Answer 2

其實這取決於你希望你的樹的工作方式，例如，如果有訂單元素之間等等。

否則，您可以使用樹上的已知算法，如果您有一個想法如何以其他語言C或Java爲例，我可以幫助將其轉換爲OCAML。

Answer 3

在過去，我用​​。 這不是一個簡單的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> 

希望這有助於

Answer 4

有一個Ptree數據類型由Matt我想，麥克唐納能夠做到你所需要的。