Scheme中n-ary树的map函数

Question

二叉树的映射函数的定义是:

(define (binary-tree-map proc tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (proc tree))
         (else (cons (binary-tree-map proc (car tree))
                     (binary-tree-map proc (cdr tree))))))

n-ary树的地图功能是什么样的？尝试:

(define (n-tree-map proc tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (proc tree))
        (else (apply map append (lambda (p)(n-tree-map proc (cdr tree)))))))

Answer 1

用cons(称为树结构)制作的每个n-ary树都将具有等效的镜像二叉树.在树上进行映射可以保持结构,从而保持cons完全相同的关系,因此运行binary-tree-mapn-ary树的结果就好像它是一个n-ary映射应该产生相同的结果.

(1 2 (3 4)) 可以解释为:

 /|\
1 2 |\
    3 4

但作为二叉树,它将是:

 /\
1 /\
 2 /\
  /\ nil
 3 /\
  4 nil

让我们试试吧!

(binary-tree-map (lambda (x) (+ x 1)) '(1 2 (3 4))) 
; ==> (2 3 (4 5))

现在,如果您以不同方式创建树.例如.记录使得节点不是一对,或者如果您需要跟踪深度,那么您需要一个不同的过程.

#!r6rs
(import (rnrs))
(define-record-type (tree make-tree tree?)
  (fields 
    (immutable children tree-children)))

(define (tree-map proc tr)
  (cond ((not (tree? tr)) (proc tr))
        (else (make-tree (map (lambda (x) (tree-map proc x)) (tree-children tr))))))

(define test-tree
        (make-tree (list '(1 2 3) 
                    '(2 3 4) 
                    '(3 4 5) 
                    (make-tree '((7 8 9) 
                            (10 11 22))))))

(tree-map cdr test-tree) 
; ==> (#tree (list '(2 3) '(3 4) '(4 5) (#tree '((8 9) (11 22)))))

请注意,列表现在可以是叶子,因为列表不是指节点.通过使用标记来标识节点,也可以使用列表结构执行此操作:

(define tree-tag (vector 'tree))
(define (tree? tr) (and (pair? tr) (eq? tree-tag (car tr))))
(define (make-tree children) (cons tree-tag children))
(define tree-children cdr)

(tree-map cdr test-tree) 
; ==> '(#(tree) (2 3) (3 4) (4 5) (#(tree) (8 9) (11 22)))