练习 2.27

deep-reverse 函数比 reverse 函数更进一步，它不仅逆序最外层的列表(树根)，而且还使用递归，连内层的子树也一并进行逆序。

;;; 27-deep-reverse.scm

(define (deep-reverse tree)
    (cond ((null? tree)         ; 空树
            '())
          ((not (pair? tree))   ; 叶子
            tree)
          (else
            (reverse (list (deep-reverse (car tree))            ; 递归地逆序左右子树
                           (deep-reverse (cadr tree)))))))

测试：

1 ]=> (load "27-deep-reverse.scm")

;Loading "27-deep-reverse.scm"... done
;Value: deep-reverse

1 ]=> (define x (list (list 1 2) (list 3 4)))

;Value: x

1 ]=> x

;Value 11: ((1 2) (3 4))

1 ]=> (reverse x)

;Value 12: ((3 4) (1 2))

1 ]=> (deep-reverse x)

;Value 13: ((4 3) (2 1))

better-deep-reverse

通过使用一些辅助函数，可以让 deep-reverse 程序更具可读性：

;;; 27-better-deep-reverse.scm

(define (deep-reverse tree)
    (cond ((empty-tree? tree)
            '())
          ((leaf? tree)
            tree)
          (else
            (reverse (make-tree (deep-reverse (left-branch tree))
                                (deep-reverse (right-branch tree)))))))

(define (empty-tree? tree)
    (null? tree))

(define (leaf? tree)
    (not (pair? tree)))

(define (make-tree left-branch right-branch)
    (list left-branch right-branch))

(define (left-branch tree)
    (car tree))

(define (right-branch tree)
    (cadr tree))

测试：

1 ]=> (load "27-better-deep-reverse.scm")

;Loading "27-better-deep-reverse.scm"... done
;Value: right-branch

1 ]=> (define x (list (list 1 2) (list 3 4)))

;Value: x

1 ]=> x

;Value 11: ((1 2) (3 4))

1 ]=> (reverse x)

;Value 12: ((3 4) (1 2))

1 ]=> (deep-reverse x)

;Value 13: ((4 3) (2 1))

tree-reverse

上面两个函数只能处理输入为二叉树的情况， 也即是，对于像 (list (list 1 2) (list 3 4)) 这样的输入， deep-reverse 和 better-deep-reverse 可以给出正确的输出， 但是，如果输入不是二叉树，那么它们的输出就不是正确的：

;; 输入为三叉树，正确输出应该是 ((6 5) (4 3) (2 1)) 才对

1 ]=> (deep-reverse (list (list 1 2) (list 3 4) (list 5 6)))

;Value 11: ((4 3) (2 1))

以下函数可以处理输入不为二叉树的情况：

;;; 27-tree-reverse.scm

(define (tree-reverse lst)
    (define (iter remained-items result)
        (if (null? remained-items)
            result
            (iter (cdr remained-items)
                  (cons (if (pair? (car remained-items))
                            (tree-reverse (car remained-items))
                            (car remained-items))
                        result))))
    (iter lst '()))

无论输入是二叉树、三叉树，等等，这个函数都可以给出正确的输出：

1 ]=> (load "27-tree-reverse.scm")

;Loading "27-tree-reverse.scm"... done
;Value: tree-reverse

1 ]=> (tree-reverse (list (list 1 2) (list 3 4)))

;Value 11: ((4 3) (2 1))

1 ]=> (tree-reverse (list (list 1 2) (list 3 4) (list 5 6)))

;Value 12: ((6 5) (4 3) (2 1))

讨论

blog comments powered by Disqus