sicp-ex-2.65


 (define (union-set tree1 tree2) 
   (list->tree (union-set-list (tree->list tree1) 
                          (tree->list tree2)))) 
  
 (define (intersection-set tree1 tree2) 
   (list->tree (intersection-set-list (tree->list tree1) 
                                 (tree->list tree2)))) 

leafac

If you want to avoid the conversions back and forth from representations, you can choose to don't use the results of exercises 2.63 and 2.64:

 (define (union-set a b) 
   (cond ((null? a) b) 
         ((null? b) a) 
         (else 
          (let ((a-entry (entry a)) 
                (a-left-branch (left-branch a)) 
                (a-right-branch (right-branch a)) 
                (b-entry (entry b)) 
                (b-left-branch (left-branch b)) 
                (b-right-branch (right-branch b))) 
            (cond ((= a-entry b-entry) 
                   (make-tree a-entry 
                              (union-set a-left-branch b-left-branch) 
                              (union-set a-right-branch b-right-branch))) 
                  ((< a-entry b-entry) 
                   (make-tree b-entry 
                              (union-set a b-left-branch) 
                              b-right-branch)) 
                  ((> a-entry b-entry) 
                   (make-tree a-entry 
                              (union-set a-left-branch b) 
                              a-right-branch))))))) 
  
 (union-set (list->tree '(1 3 5)) 
            (list->tree '(2 3 4))) 
 ;; => (3 (2 (1 () ()) ()) (5 (4 () ()) ())) 
  
 ;warning this algo has wrong output 
 ;; check input as bst1 bst2 as: 
 ; (define bst1 (list->tree '(1 2 3 4 5 6 7))) 
 ; (define bst2 (list->tree '(6 7 8 9))) 
 (define (intersection-set a b) 
   (cond ((null? a) ()) 
         ((null? b) ()) 
         (else 
          (let ((a-entry (entry a)) 
                (a-left-branch (left-branch a)) 
                (a-right-branch (right-branch a)) 
                (b-entry (entry b)) 
                (b-left-branch (left-branch b)) 
                (b-right-branch (right-branch b))) 
            (cond ((= a-entry b-entry) 
                   (make-tree a-entry 
                              (intersection-set a-left-branch b-left-branch) 
                              (intersection-set a-right-branch b-right-branch))) 
                  ((< a-entry b-entry) 
                   (union-set 
                    (intersection-set a-right-branch 
                                      (make-tree b-entry () b-right-branch)) 
                    (intersection-set (make-tree a-entry a-left-branch ()) 
                                      b-left-branch))) 
                  ((> a-entry b-entry) 
                   (union-set 
                    (intersection-set (make-tree a-entry () a-right-branch) 
                                      b-right-branch) 
                    (intersection-set a-left-branch 
                                      (make-tree b-entry b-left-branch ()))))))))) 
  
 (intersection-set (list->tree '(3 5 10)) 
                   (list->tree '(1 2 3 4 5 7))) 
 ;; => (5 (3 () ()) ()) 
  

anohter solution

  
 (define (addjoin x set) 
   (cond ((null? set) (make-tree x '() '())) 
         ((= x (entry set)) set) 
         ((< x (entry set)) (make-tree (entry set) (addjoin x (left-branch set)) (right-branch set))) 
         ((> x (entry set)) (make-tree (entry set) (left-branch set) (addjoin x (right-branch set)))))) 
 (define (element-of? x set) 
   (cond ((null? set) false) 
         ((= x (entry set)) true) 
         ((< x (entry set)) (element-of? x (left-branch set))) 
         ((> x (entry set)) (element-of? x (right-branch set))))) 
 (define (union-set set1 set2) 
   (cond ((null? set1) set2) 
         (else 
          (let ((result-entry (addjoin (entry set1) set2))) 
            (let ((left-result (union-set (left-branch set1) result-entry))) 
              (union-set (right-branch set1) left-result)))))) 
 (define (intersection-set set1 set2) 
   (cond ((null? set1) '()) 
         ((null? set2) '()) 
         ((element-of? (entry set1) set2) 
          (make-tree (entry set1) 
                     (intersection-set (left-branch set1) set2) 
                     (intersection-set (right-branch set1) set2))) 
         (else 
          (union-set (intersection-set (left-branch set1) set2) 
                     (intersection-set (right-branch set1) set2))))) 
  
 ;next is annother list->tree 
 (define (sub-lst lst a b) 
     (define (iter lst index a b result) 
       (cond ((or (null? lst) (> index b)) result) 
             ((< index a) (iter (cdr lst) (+ index 1) a b result)) 
             (else 
              (iter (cdr lst) (+ index 1) a b (append result (list (car lst))))))) 
     (iter lst 0 a b '())) 
 (define (list->tree2 lst) 
   (let* ((n (length lst)) 
         (part (quotient (- n 1) 2))) 
     (cond ((= n 0) '()) 
           ((= n 1) (make-tree (car lst) '() '())) 
           (else 
            (let ((left-part (sub-lst lst 0 (- part 1))) 
                  (right-part (sub-lst lst part n))) 
              (let ((entry (car right-part))) 
                (make-tree entry  
                           (list->tree2 left-part) 
                           (list->tree2 (cdr right-part))))))))) 
  


<< Previous exercise (2.64) | Index | Next exercise (2.66) >>