乐正

Actions speak louder than words.

Sicp-ex2-65

问题

利用练习2.63和练习2.64的结果,请给出采用(平衡)二叉树方式实现的集合的union-setintersection-set操作的$\Theta (n)$的实现。

解答

练习2.65 (ex2-65.scm) download
1
2
3
4
5
6
7
8
9
(define (union-tree a-tree b-tree)
  (list->tree
    (union-set (tree->list-2 a-tree)
               (tree->list-2 b-tree))))

(define (intersection-tree a-tree b-tree)
  (list->tree
    (intersection-set (tree->list-2 a-tree)
                      (tree->list-2 b-tree))))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;; (load 'p102-intersection-set.scm)
;; (load 'ex2-62.scm)
;; (load 'p105-tree.scm)
;; (load 'p108-tree->list-2.scm)

(define a-tree (make-tree 7
                          (make-tree 5 '() '())
                          (make-tree 9 '() '())))
;Value: a-tree

(define b-tree (make-tree 10
                          (make-tree 5 '() '())
                          (make-tree 21 '() '())))
;Value: b-tree

(union-tree a-tree b-tree)
;Value 21: (9 (5 () (7 () ())) (10 () (21 () ())))

(intersection-tree a-tree b-tree)
;Value 22: (5 () ())

draft

« sicp-ex2-64 sicp-ex2-66 »

Comments