квадратные числа в дереве с использованием сгиба - PullRequest
Новая
       23

квадратные числа в дереве с использованием сгиба

0 голосов
/ 05 марта 2020

Цель состоит в том, чтобы создать дерево со всеми квадратами чисел, используя функцию дерева сгиба. Кстати, это не домашнее задание. Так что я могу свободно это обсуждать. 

; A Tree-Of-Numbers is one of:
; - (make-node Tree-Of-Numbers Number Tree-Of-Numbers)
; - EmptyTree
; interp. a tree with numbers stored at its nodes.

(define-struct node (left value right))

; An EmptyTree is a structure (make-empty-tree))
; interp. an empty tree

(define-struct empty-tree ())

(define EXAMPLE-TREE
  (make-node (make-node (make-node EMPTY 6 EMPTY)
                        20 EMPTY) 8 (make-node (make-node EMPTY 14 EMPTY)
                        42 (make-node EMPTY 2 EMPTY))))

(define EMPTY (make-empty-tree))

Я запрограммировал функцию дерева сгиба: 


(define (fold-tree f b tree)
  (cond
    [(empty-tree? tree) b]
    [else (f (node-value tree)
             (fold-tree f b (node-left tree))
              (fold-tree f b (node-right tree)))]))

Теперь я должен использовать эту функцию для возведения в квадрат всех чисел в дереве. Я могу сделать это другими способами, например так: 

(define (sqr-tree tree)
  (cond
    [(empty-tree? tree) EMPTY]
    [(node? tree) (make-node (sqr-tree (node-left tree))
                                 (sqr (node-value tree))
                                 (sqr-tree (branch-right tree)))]))

Я также смог сделать это, написав функцию дерева карт и используя ее для возведения в квадрат всех чисел в дереве. Но вопрос в том, как это сделать с помощью фолд-дерева?

1 Ответ

0 голосов
/ 05 марта 2020

Если все вспомогательные процедуры верны, это должно сработать: 

(define (sqr-tree tree)
  (fold-tree (lambda (value left right)
               (make-node left (sqr value) right))
             EMPTY
             tree))
...