On Friday 30 November 2007 03:19, Ashish Agarwal wrote:

> Are there any simple tree data structure implementations? All I find is

> fancier stuff like binary search trees, AVL trees, etc. But I just want the

> most simple tree. A tree is a leaf node or a node with some sub-trees.

# type 'a tree = Node of 'a * 'a tree list;;

type 'a tree = Node of 'a * 'a tree list

> Insertion requires specifying the parent node to insert under.

Not usually in OCaml, where trees are immutable.

> There should be methods for traversing the tree in depth-first or

> breadth-first order. It should be easy to implement, but that's why I'm

> hoping its already been done.

# let rec depth_first f (Node(x, ts)) =

f x;

List.iter (depth_first f) ts;;

val depth_first : ('a -> 'b) -> 'a tree -> unit = <fun>

# let rec breadth_first f = function

| [] -> ()

| ts ->

breadth_first f

(List.flatten

(List.map (function Node(x, ts) -> f x; ts) ts));;

val breadth_first : ('a -> 'b) -> 'a tree list -> unit = <fun>

# let example =

Node ("root",

[Node ("left", [Node ("ll", []); Node ("lr", [])]);

Node ("right", [Node ("rl", []); Node ("rr", [])])]);;

val example : string tree =

Node ("root",

[Node ("left", [Node ("ll", []); Node ("lr", [])]);

Node ("right", [Node ("rl", []); Node ("rr", [])])])

# depth_first print_endline example;;

root

left

ll

lr

right

rl

rr

# breadth_first print_endline [example];;

root

left

right

ll

lr

rl

rr

Interrupted.

--

Dr Jon D Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/products/?e