type 'a llist = LEmpty | LCons of 'a * (unit -> 'a llist);;
module BST :
sig
(*type 'a llist*)
val create: unit -> unit
val push: 'a -> unit
val remove: int -> unit
val find: int -> bool
val getBFS: unit -> int llist
val getDFS: unit -> int llist
val llistToNormal: int llist -> int list
end=
struct
(*type 'a llist = LEmpty | LCons of 'a * (unit -> 'a llist)*)
type 'a nnode = Empty | Node of 'a * 'a nnode * 'a nnode
let root = ref Empty
(* If root isn't empty, function clears it *)
let create() = root := Empty
(* Add item to tree *)
let push(elem) =
let rec add = function
| Node(v, l, r) -> if elem > v then
Node(v, l, add r)
else
Node(v, add l, r)
| Empty -> Node(elem, Empty, Empty)
in root := add(!root)
(* Search for successor of specified node and remove it*)
let rec findSuccessor = function
| Node(v, l, r) ->
if l = Empty then (v, r)
else
let (value, result) = findSuccessor(l) in
(value, Node(v, result, r))
| Empty -> Null, Empty
(* Remove specified item from the tree *)
let remove(elem) =
let rec removeNode = function
| Node(v, l, r) ->
if v = elem then
let (value, result) = findSuccessor(r) in
if result = Empty then
l
else
Node(value, l, result)
else
if elem < v then
Node(v, removeNode l, r)
else
Node(v, l, removeNode r)
| Empty -> Empty
in root := removeNode(!root)
(* Find element in the tree *)
let find(elem) =
let rec find = function
| Node(v, l, r) ->
if v = elem then true
else
if elem < v then find(l)
else find(r)
| Empty -> false
in find(!root)
(* Create lazy list out of tree nodes using DFS preorder algorithm*)
let getDFS() =
let rec depth = function
| [] -> LEmpty
| Empty::t -> depth(t)
| Node(v, l, r)::t -> LCons(v, fun() -> depth( [l; r] @ t))
in depth [!root]
(* Create lazy list out of tree nodes using BFS algorithm*)
let getBFS()=
let rec breadth = function
| [] -> LEmpty
| Empty::t -> breadth(t)
| Node(v, l, r)::t -> LCons(v, fun() -> breadth( t @ [l; r] ))
in breadth [!root]
(* Transform lazy list to normal *)
let rec llistToNormal = function
| LCons(v, f) -> v::llistToNormal(f())
| LEmpty -> []
end;;
BST.create();;
BST.push(5);;
BST.push(4);;
BST.push(3);;
BST.push(2);;
BST.push(1);;
BST.remove(3);;
BST.llistToNormal(BST.getBFS());;
BST.create();;
BST.push(5);;
BST.push(3);;
BST.push(4);;
BST.push(1);;
BST.push(8);;
BST.push(9);;
BST.push(7);;
BST.llistToNormal(BST.getBFS());;
BST.llistToNormal(BST.getDFS());;
{"html5":"htmlmixed","css":"css","javascript":"javascript","php":"php","python":"python","ruby":"ruby","lua":"text\/x-lua","bash":"text\/x-sh","go":"go","c":"text\/x-csrc","cpp":"text\/x-c++src","diff":"diff","latex":"stex","sql":"sql","xml":"xml","apl":"apl","asterisk":"asterisk","c_loadrunner":"text\/x-csrc","c_mac":"text\/x-csrc","coffeescript":"text\/x-coffeescript","csharp":"text\/x-csharp","d":"d","ecmascript":"javascript","erlang":"erlang","groovy":"text\/x-groovy","haskell":"text\/x-haskell","haxe":"text\/x-haxe","html4strict":"htmlmixed","java":"text\/x-java","java5":"text\/x-java","jquery":"javascript","mirc":"mirc","mysql":"sql","ocaml":"text\/x-ocaml","pascal":"text\/x-pascal","perl":"perl","perl6":"perl","plsql":"sql","properties":"text\/x-properties","q":"text\/x-q","scala":"scala","scheme":"text\/x-scheme","tcl":"text\/x-tcl","vb":"text\/x-vb","verilog":"text\/x-verilog","yaml":"text\/x-yaml","z80":"text\/x-z80"}