src/sicp/ex2_64.clj

   1 (ns sicp.ex2_64
   2   (:use [sicp.ch2_3 :only (make-tree)]))
   3
   4 (declare partial-tree)
   5
   6 (defn list->tree [elements]
   7   (first (partial-tree elements (count elements))))
   8
   9 (defn partial-tree [elts n]
  10   (if (= n 0)
  11     (cons '() elts)
  12     (let [left-size     (quot (- n 1) 2)
  13           left-result   (partial-tree elts left-size)
  14           left-tree     (first left-result)
  15           non-left-elts (rest left-result)
  16           right-size    (- n (+ left-size 1))
  17           this-entry    (first non-left-elts)
  18           right-result  (partial-tree (rest non-left-elts) right-size)
  19           right-tree    (first right-result)
  20           remaining-elts (rest right-result)]
  21       (cons (make-tree this-entry
  22                        left-tree
  23                        right-tree)
  24             remaining-elts))))
  25
  26 (comment
  27   "partial-tree divides the input sequence roughly into 2 halfs and creates a tree of
  28    partial-trees on each of the branches."
  29   "The tree for the input '(1 3 5 7 9 11) looks like this:"
  30   "
  31           5
  32         /   \\r
  33        1     9
  34         \   / \\r
  35          3 7   11
  36   "
  37   "partial-tree does a cons for every element of the list. So, order of growth is O(n)."
  38 )