【SICP练习】92 练习2.65

练习2.65

最后一道题了，来个总结倒是很不错。要完成两个函数，我们就要用到前面所学，首先用练习2.63中的函数将树变成表，这样有利于后续的处理，而根据前面的习题，用tree->list-2会更加快速。然后要实现并集或补集的功能，也要用到第104页相关的函数。题目要求的是平衡二叉树，因此还要用到练习2.64中的list->tree函数将最后的结果平衡。这三个函数的复杂度都出奇的一致为n，因此最终的函数的复杂度也为n。因为其中要用到intersection-set等函数，因此我们将最终题目所求的函数稍微改下名。

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

相信大家已经看到了，这道题并不难，只要我们能够想到运用前面所学的知识。