Skip to content

Instantly share code, notes, and snippets.

@lynxor

lynxor/binary_search_tree.clj

Last active December 17, 2015 03:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lynxor/5547367 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lynxor/5547367 to your computer and use it in GitHub Desktop.
Download ZIP
binary search tree
Raw
binary_search_tree.clj
(defn tconj [v t]
(cond (nil? t)
{:value v :left nil :right nil}
(< v (:value t))
{:value (:value t) :left (tconj v (:left t)) :right (:right t) }
(> v (:value t))
{:value (:value t) :left (:left t) :right (tconj v (:right t) ) }
:else t ;no dupes
))
(defn breadth-first [root visit]
(letfn [(doit [[head & tail]]
(visit (:value head))
(let [newq (filter #(not (nil? %)) (concat tail [(:left head) (:right head)] ))]
(if (not (empty? newq))
(recur newq))))]
(doit [root])))
(defn tfind [v t]
(cond (nil? t) false
(= (:value t) v) true
(< v (:value t)) (tfind v (:left t))
:else (tfind v (:right t))))
(defn tconj-all [t [v & rest]]
(if (empty? rest)
(tconj v t)
(tconj-all (tconj v t) rest)))
(defn tseq [t trans]
(letfn [(go [t]
(if (not (nil? t))
(concat (go (:left t)) [(trans t)] (go (:right t))) ))]
(go t)))
(def valueT #(:value %))
;does not compare length :(
(defn tcmp [t1 t2]
(reduce (fn [acc v] (and acc (tfind v t2))) true (tseq t1 valueT) ))
; Using it:
(def tree1 (tconj-all nil [5 3 10 2 4 12 15 7 8 9 0]))
(def tree2 (tconj-all nil [3 10 2 4 12 5 15 7 8 9 0]))
; (breadth-first tree1 println)
; (println (map valueT (tseq tree1 identity ) ))
; (println (= (tseq tree1 valueT) (tseq tree2 valueT)))
; (doseq [it (concat [17 19 21] (tseq tree1 valueT))]
; (println it " - " (tfind it tree1)))
(print (tcmp tree1 tree2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment