方案更改树值

写下可能的输入是什么(在树的描述中有三种情况),并定义每种情况的结果。

以下是您需要实现的常规树遍历:

• 如果树为空:
  • 生成空树
• 如果树是一片叶子:
  • 产生一个倒转的叶子
• 否则:
  • 反转节点的值
  • 通过将此反转值与反转每个子树的结果相结合,生成一棵新树

你可能会想了解 map 在您最喜欢的方案书中。

有可能(但我怀疑这是稍后的练习)将其推广,以便在树中应用任意函数,就像 地图 对列表执行。

对树结构的解释似乎不起作用。 (1 (-2) (3) 是节点,但 1 不是父级。然而,您似乎可以将整个过程视为一棵二叉树,其中对是节点,空列表是一棵空树,任何其他值都是叶节点。

抽象如下所示:

(define make-tree cons)
(define tree-left car)
(define tree-right cdr)
(define tree? pair?)
(define empty-tree '())

可以像这样映射树的值:

(define (map-tree proc tree)
  (cond ((eq? empty-tree tree) empty-tree)
        ((tree? tree) 
         (make-tree (map-tree proc (tree-left tree))
                    (map-tree proc (tree-right tree))))
        (else (proc tree))))

示例:

(map-tree (lambda (v) (+ v 1)) '(1 (2) 3))
; ==> (2 (3) 4)

显然,您需要用如下过程替换第一个参数:

(inverse #f) ; ==> #t
(inverse #t) ; ==> #f
(inverse 5)  ; ==> -5
;; optional
(inverse 'xxx) ; ==> xxx

这样就很容易制定您的程序:

(define (inverse-tree tree)
  (map-tree inverse tree))

(inverse-tree ’(-5 (1 (-2) (3) (#f)) (#t)))
; ==> (5 (-1 (2) (-3) (#t)) (#f))

现在,如果不能使用抽象,则需要使用替换规则。例如:。

(define (tree-inc v)
  (map-tree (lambda (v) (+ v 1)) v))

; ==
(define (tree-inc tree)
  (cond ((eq? '() tree) '())
        ...
        (else (+ (car tree) 1))))

给你。比使用抽象的更难阅读和推理。祝你好运。

在深入挖掘和更好地理解语法后,我找到了一个简单的1函数解决方案:

(define (inverse-tree tree)
  (cond ((eq? '() tree) '())
        ((pair? tree) 
         (cons (inverse-tree (car tree))
                    (inverse-tree (cdr tree))))
        (else ((lambda(x) (if (boolean? x) (not x) (- x))) tree))))

我认为应该这样做:

  (define inverse-tree
  (lambda (tree)
    (if (null? tree)
        '()
        (if (number? (car tree))
            (cons (* -1 (car tree)) (inverse-tree (cdr tree)))
            (if (boolean? (car tree))
                (cons (not (car tree)) (inverse-tree (cdr tree)))
                (cons (inverse-tree (car tree)) (inverse-tree (cdr tree))))))))