Representing A Tree in Clojure

Question

What would be a idiomatic way to represent a tree in Clojure?

     A
    / \
   B   C
  /\    \
 D  E    F

Such as the one above, performance is not important and tree's wont grow more than 1k elements.

Answer 1

There's a scary way of doing it using just cons:

(defn mktree 
  ([label l r] (cons label (cons l r))) 
  ([leaf] (cons leaf (cons nil nil))))
(defn getlabel [t] (first t))
(defn getchildren [t] (rest t))
(defn getleft [t] (first (getchildren t)))
(defn getright [t] (rest (getchildren t)))

Note that children isn't a list; it's a pair. If your trees aren't just binary, you could make it a list. use nil when there's no left or right child, of course.

Otherwise, see this answer.

The tree in your picture:

(mktree 'A (mktree 'B (mktree 'D) (mktree 'E)) (mktree 'C nil (mktree 'F)))

Answer 2

You should probably use a struct for this.

(defstruct bintree :left :right :key)

You can use struct-map to instantiate the structure.

(struct-map bintree :left nil :right nil :key 0)

Answer 3

Tree's underly just about everything in clojure because they lend them selves so nicely to structural sharing in persistent data structure. Maps and Vectors are actually trees with a high brancing factor to give them bounded lookup and insert time. so the shortest answer i can give (though its not really that useful) is I really recommend Purely functional data structures by Chris Okasaki for a real answer to this question. also Rich Hicky's video on clojure data ctructures on blip.tv

(set 'A 'B 'C)

Answer 4

'(A (B (D) (E)) (C (F)))