这里实现的 union-set 与 intersection-set 可以使用前面一小节中的结果。我们知道了一个用有序表来实现的集合的 union-set 与 intersection-set 增长阶为 O(n)，所以我们的树可以直接转化为有序表然后进行求交集与并集。树转为表需要 O(n)，表转为树需要 O(log(n))，所以整体的阶依然是 O(n)。

(define (union-set set1 set2)
  (define (union-ordered-list lst1 lst2)
    (cond ((null? lst1) lst2)
          ((null? lst2) lst1)
          ((= (car lst1) (car lst2))
           (cons (car lst1)
                 (union-ordered-list (cdr lst1) (cdr lst2))))
          ((> (car lst1) (car lst2))
           (cons (car lst2)
                 (union-ordered-list lst1 (cdr lst2))))
          (else
           (cons (car lst1)
                 (union-ordered-list (cdr lst1) lst2)))))  
  (let ((set1-list (tree->list set1))
        (set2-list (tree->list set2)))
    (list->tree (union-ordered-list set1-list set2-list))))

;;; intersection-set
(define (intersection-set set1 set2)
  (define (intersection-ordered-list lst1 lst2)
    (cond ((or (null? lst1) (null? lst2)) '())
          ((= (car lst1) (car lst2))
           (cons (car lst1)
                 (intersection-ordered-list (cdr lst1) (cdr lst2))))
          ((> (car lst1) (car lst2))
           (intersection-ordered-list lst1 (cdr lst2)))
          (else
           (intersection-ordered-list (cdr lst1) lst2))))  
  (let ((set1-list (tree->list set1))
        (set2-list (tree->list set2)))
    (list->tree (intersection-ordered-list set1-list set2-list))))

测试时，则需要保证生成的树的正确性，如果我们需要使用二叉树来表示，那么我们不得不在生成树的时候使用 sort 过程先排序再转化为树（这是我们之前没有考虑的时间支出的部分）。

(load "../testframe.scm")

; element-of-set?
(asserttrue (element-of-set? 1 (list->tree '(1 2 3))))

(asserttrue (element-of-set? 1 (list->tree '(2 1 3))))

(asserttrue (element-of-set? 1 (list->tree '(2 3 1))))

; adjoin-set
(assertequal? (tree->list (adjoin-set 1 (list->tree '(2 3 4))))
              '(1 2 3 4))

(assertequal? (tree->list (adjoin-set 1 (list->tree '(1 2 3))))
              '(1 2 3))

; intersection-set
(assertequal? (intersection-set (list->tree '(1 2 3)) (list->tree '(4 5 6)))
              '())

(assertequal? (tree->list (intersection-set (list->tree '(1 2 3)) (list->tree '(2 3 4))))
              '(2 3))

(assertequal? (tree->list (intersection-set (list->tree '(1 2 3)) (list->tree '(1 2 3 4))))
              '(1 2 3))

(assertequal? (tree->list (intersection-set (list->tree '(1 2 3 4)) (list->tree '(1 2))))
              '(1 2))

; union-set
(assertequal? (tree->list (union-set (list->tree '(1 2 3)) (list->tree '(3 4 5))))
              '(1 2 3 4 5))

(assertequal? (tree->list (union-set (list->tree '(1 2 3)) (list->tree '(1 2 3 4))))
              '(1 2 3 4))

(assertequal? (tree->list (union-set (list->tree '(1 2 3 4)) (list->tree '(1 2 3))))
              '(1 2 3 4))

(assertequal? (tree->list (union-set (list->tree '(1 2 3)) (list->tree '(4 5 6))))
              '(1 2 3 4 5 6))