Note
为了避免和所使用的辅助程序发生重名冲突，本题的 intersection-set 被改名为 intersection-tree ， union-set 被改名成 union-tree 。
使用树实现的 \(\Theta(n)\) 复杂度的 intersection-tree 和 union-tree 的步骤如下：
tree->list-2 程序，将输入的两棵树转换成两个列表，复杂度 \(\Theta(n)\) 。intersection-set 计算两个列表的交集；如果要执行的是并集操作，那么使用 练习 2.62 的 union-set 计算两个列表的并集；以上两个程序的复杂度都是 \(\Theta(n)\) 。list->tree 程序，将第二步操作所产生的列表转换成一棵平衡树，复杂度为 \(\Theta(n)\) 。intersection-tree 和 union-tree 的整个过程需要使用三个复杂度为 \(\Theta(n)\) 的程序，但总的复杂度还是 \(\Theta(n)\) ，因此符合题目的要求。
定义：
;;; 65-intersection-tree.scm
(load "63-tree-list-2.scm")
(load "64-list-tree.scm")
(load "p105-intersection-set.scm")
(define (intersection-tree tree another)
(list->tree
(intersection-set (tree->list-2 tree)
(tree->list-2 another))))
测试：
1 ]=> (load "65-intersection-tree.scm")
;Loading "65-intersection-tree.scm"...
; Loading "63-tree-list-2.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "64-list-tree.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "p105-intersection-set.scm"... done
;... done
;Value: intersection-tree
1 ]=> (define it (intersection-tree (list->tree '(1 2 3 4 5))
(list->tree '(1 3 5 7 9))))
;Value: it
1 ]=> it
;Value 11: (3 (1 () ()) (5 () ()))
1 ]=> (tree->list-2 it)
;Value 12: (1 3 5)
定义：
;;; 65-union-tree.scm
(load "62-union-set.scm")
(load "63-tree-list-2.scm")
(load "64-list-tree.scm")
(define (union-tree tree another)
(list->tree
(union-set (tree->list-2 tree)
(tree->list-2 another))))
测试：
1 ]=> (load "65-union-tree.scm")
;Loading "65-union-tree.scm"...
; Loading "62-union-set.scm"... done
; Loading "63-tree-list-2.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "64-list-tree.scm"...
; Loading "p106-tree.scm"... done
; ... done
;... done
;Value: union-tree
1 ]=> (define ut (union-tree (list->tree '(1 2 3 4 5))
(list->tree '(1 3 5 7 9))))
;Value: ut
1 ]=> Ut
;Value 12: (4 (2 (1 () ()) (3 () ())) (7 (5 () ()) (9 () ())))
1 ]=> (tree->list-2 ut)
;Value 13: (1 2 3 4 5 7 9)