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))
通过使用一些辅助函数,可以让 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))
上面两个函数只能处理输入为二叉树的情况,
也即是,对于像 (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))