src/sicp/ex2_63.clj

   1 (ns sicp.ex2_63
   2   (:use [sicp.ch2_3 :only (entry left-branch right-branch)]
   3         [clojure.test]))
   4
   5 (defn tree->list-1 [tree]
   6   (if (empty? tree)
   7     '()
   8     (concat (tree->list-1 (left-branch tree))
   9             (cons (entry tree)
  10                   (tree->list-1 (right-branch tree))))))
  11
  12 (defn tree->list-2 [tree]
  13   (let [copy-to-list (fn f [tree result-list]
  14                        (if (empty? tree)
  15                          result-list
  16                          (f (left-branch tree)
  17                             (cons (entry tree)
  18                                   (f (right-branch tree) result-list)))))]
  19     (copy-to-list tree '())))
  20
  21 (deftest test-for-some-trees
  22   (are [x y] [= x y]
  23        (tree->list-1 '(7 (3 (1 ()) (5 ())) (9 () (11 ())))) '(1 3 5 7 9 11)
  24        (tree->list-2 '(7 (3 (1 ()) (5 ())) (9 () (11 ())))) '(1 3 5 7 9 11)
  25        (tree->list-1 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))) '(1 3 5 7 9 11)
  26        (tree->list-2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))) '(1 3 5 7 9 11)
  27        (tree->list-1 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))) '(1 3 5 7 9 11)
  28        (tree->list-2 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))) '(1 3 5 7 9 11)))
  29
  30 ;;;; part a
  31 (comment
  32   "yes, as the above tests show, they add elements into the list in the same order
  33    and hence produce same lists."
  34 )
  35
  36 ;;;; part b
  37 (comment
  38   "tree->list-1 does a cons and an append of two lists at every step. The depth of the
  39    tree is log(n). append grows as length of the list. The number of steps required to
  40    traverse down to the tree is log(n). So, this is a O(n.log(n)) operation."
  41
  42   "list->tree-2 does only a cons operation at every step. So this is a O(n) operation."
  43 )