f# - ノード二分木を挿入

Question

私はこのツリーノードを持っています:

type Tree<'T when 'T: comparison> = 
| Empty 
| Node of 'T * Tree<'T> * Tree<'T>

しかし、私は良い挿入機能を見つけることができません。

私はインタラクティブなプログラムをしたくありません。入力は、ツリーに挿入されるリストでなければなりません。

Answer 1

ツリーのバランスをとる必要がない場合は、次を使用できます。

let rec insert value = function
| Empty -> Node(value, Empty, Empty)
| Node(v, left, right) when value < v -> Node(v, insert value left, right)
| Node(v, left, right) when value > v -> Node(v, left, insert value right)
| Node(_, _, _) as n -> n

次の方法で、値のリストをツリーに挿入できます。

let insertAll list tree = List.fold (fun t e -> insert e t) tree list