Scheme中n叉树的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 元树的映射函数是什么样的？尝试过：

(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 叉树（称为树结构）都将有一个镜像二叉树等价物。在树上映射保持结构，因此所有 cons 保持完全相同的关系，因此运行你的 binary-tree-map 在 n 元树上的结果就好像它是 n 元一样地图应该产生相同的结果。

(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)))

Answer 2

简短回答，该函数很适合用于 n 叉树。假设您直接使用语言原语而不是 ADT（抽象数据类型）。一种表示 n 元树的方法是这样的...

(define (make-n-ary-tree node . children)
 (cons node children))

此实现与您的函数结合使用时唯一奇怪的地方是它会在子树的末尾添加一个额外的空树）

在处理树或其他复杂数据类型时，构造一个 ADT 是理想的，或者在您的评论中说明表示的含义。

请记住，计算机不会对您的数据的含义大惊小怪。作为程序员，您必须非常小心地保持一致的含义和语义。

Scheme中n叉树的map函数

map function for n-ary tree in Scheme

lisp

tree

scheme

functional-programming