CODEWITHSUNDEEP
data-structuresclojure
Hamza Yerlikaya
Hamza Yerlikaya

Reputation: 49329

Representing A Tree in Clojure

What would be an idiomatic way to represent a tree in Clojure? E.g.:

     A
    / \
   B   C
  /\    \
 D  E    F

Performance is not important and the trees won't grow past 1000 elements.

Upvotes: 49

Views: 11274

Answers (3)

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91534

Trees underly just about everything in Clojure because they lend themselves so nicely to structural sharing in persistent data structure. Maps and Vectors are actually trees with a high branching factor to give them bounded lookup and insert time. So the shortest answer I can give (though it's not really that useful) is that I really recommend Purely functional data structures by Chris Okasaki for a real answer to this question. Also Rich Hickey's video on Clojure data structures on blip.tv

(set 'A 'B 'C)

Upvotes: 3

user21037
user21037

Reputation: 

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

Upvotes: 39

Jonathan Graehl
Jonathan Graehl

Reputation: 9301

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)))

Upvotes: 5

Related Questions