src/sicp/ex2_63.rkt

   1 #lang racket
   2
   3 (require "ch2_3_3_sets_as_trees.rkt")
   4
   5 (define (tree->list-1 tree)
   6   (if (null? tree)
   7       '()
   8       (append (tree->list-1 (left-branch tree))
   9               (cons (entry tree)
  10                     (tree->list-1 (right-branch tree))))))
  11
  12 (define (tree->list-2 tree)
  13   (define (copy-to-list tree result-list)
  14     (if (null? tree)
  15         result-list
  16         (copy-to-list (left-branch tree)
  17                       (cons (entry tree)
  18                             (copy-to-list (right-branch tree)
  19                                           result-list)))))
  20   (copy-to-list tree '()))
  21
  22 ;; part a. Yes, both of them give the same results.
  23
  24 (define l1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
  25 (define l2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
  26 (define l3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))
  27
  28 (tree->list-1 l1)
  29 (tree->list-1 l2)
  30 (tree->list-1 l3)
  31
  32 (tree->list-2 l1)
  33 (tree->list-2 l2)
  34 (tree->list-2 l3)
  35
  36 (provide tree->list-1 tree->list-2)
  37
  38 ;; part b.
  39 #|
  40 for tree->list-1, it does a cons and an append at each step. append needs to be done
  41 for each element of the first list. In this case the first list initially will have
  42 n/2 elements, then n/4 and so on. So, it has about O(logn) steps. Now, it also does
  43 a cons on each element, so overall it takes O(n Log n) steps.
  44
  45 for tree->list-2, it does a cons on each element, so steps is O(n).
  46
  47 Order of growth for both the procedures is O(n).
  48 |#