OCaml：ツリー関数

Question

ツリーを扱うモジュールや関数はありますか？私はゴーグルを使用しましたが、何かを見つけることができませんなど

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

と私は挿入を行うのに苦労してる、サブツリーの除去、

：私はこのようになりますタイプを持っています。

Answer 1

OCaml標準ライブラリのソースでmodule Setの実装を読んでください。 これらはバイナリツリーで実装されていますが、あなたのものよりも少し洗練されています。

（私はあなたが定義されているように見えるとして、あなたが代わりに子供たちのリストを持っていることの二分木で始まるをお勧めします）

Answer 2

順序がある場合は実際に、それは例えば、あなたがあなたのツリーが仕事をしたい方法によって異なり要素間など。

それ以外の場合は、ツリー上の既知のアルゴリズムを使用することができます。他の言語のCやJavaなどでどのように使用できるか分かっている場合は、OCAMLに変換する手助けができます。

Answer 3

以前は、​​を使用しました。 これは使用するための簡単なライブラリではありませんが、ノードを挿入してパスを変更する必要がある場合、それはトリックかもしれませんが、私はBツリーのコンテキストでこれを使ったことはありません...

言語のドキュメント：

バリアント型 の最も一般的な使用方法は、再帰的なデータに 構造を記述することです。いずれかである 空であるか、または バイナリツリー型 の値を含む「（任意のタイプ）：

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

この定義は、以下のように読み取る：バイナリツリーの タイプ、例えば検討タイプ 'aの値が1つの のノードとタイプ' a、 の2つの 'btreeの値も含む2つのサブツリー が含まれています。

バイナリツリー上の操作は、同じ構造体 の後に再帰的に表現された関数 として自然に型定義自体として表現されます。

#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データ型があります： たとえば、ここに 注文バイナリツリー（左から右に要素 増加）での検索と挿入を実行する機能 ですあなたが必要とすることをするMcDonnell、私は思う。