Как создать двоичное дерево с уникальными индексами в F #

Question

Как вы пишете рекурсивную функцию для построения двоичного дерева, где листы (значение, индекс) с индексом имеют уникальное последовательное целое число?

Текущий код что-то вроде:

let rec MakeTree size = 
    if size = 0 then 0 else 
     match ran.Next (3) with 
     | 0 -> Cow (MakeTree (size-1),MakeTree (size-1)) 
     | 1 -> Dog (MakeTree (size-1),MakeTree (size-1)) 
     | 2 -> Cat (MakeTree (size-1),MakeTree (size-1)) 

Answer 1

Вот версия без значений, но они легко добавить:

Определим дерево как:

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

И сделать вставка функция, подобная

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