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

Revisions

  1. lynxor renamed this gist May 9, 2013. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.clj → binary_search_tree.clj
    View file
    File renamed without changes.
  2. lynxor renamed this gist May 9, 2013. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.txt → gistfile1.clj
    View file
    File renamed without changes.
  3. lynxor created this gist May 9, 2013.
    62 changes: 62 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,62 @@
    (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))