Получение суммы элементов в дереве в схеме - PullRequest
Новая
       13

Получение суммы элементов в дереве в схеме

0 голосов
/ 01 ноября 2019

Напишите процедуру, (fold-right-tree op id tree), которая собирает листья дерева, используя op, аналогично сгибанию вправо в списках. Поэтому, если дерево имеет значение 

(((1 2)
  3)
 (4
  (5 6))
 7
 (8 9 10))

, тогда 

(fold-right-tree + 0  tree)

имеет значение 55.

- я хотел определить код, который суммирует все элементы в дереве 

 ;;----------

    (#%require racket)
    (define nil empty) 


    (define (reduce op init lst)
      (if (null? lst)
          init
          (op (car lst)
              (reduce op init (cdr lst)))))

    (define fold-right reduce)


    (define (sum-list lst)
      (if (null? lst) 0
          (+ (car lst) (sum-list (cdr lst)))
        ))

(define (leaf? x)
  (not (pair? x)))


    (define (fold-right-tree op init tree)
        (lambda (tree)
          (if (null? tree)
              0
              (if (leaf? tree)
                  (sum-list (list tree))
                  (fold-right op init (map fold-right-tree op init tree))))))


    (fold-right-tree (lambda (x,y) (+ x y)) 0 '((1) (2 3 4) (((5)))) )

Выходные данные должны возвращать сумму элементов дерева, но возвращает #<procedure>

в чем моя проблема?

Я также пробовал эту проблему, но на этот раз я получил сообщение об ошибке дляотображение 

(define (fold-right-tree op init tree)
      (if (null? tree)
          0
          (if (leaf? tree)
              (fold-right op init (list tree))
              (+ (fold-right-tree op init (map car tree)) (fold-right-tree op init (map cdr tree))))))


(fold-right-tree sum 0 '((1) (2 3 4) (((5)))) )

Ответы [ 2 ]

0 голосов
/ 07 ноября 2019

При наличии подходящих методов доступа и предикатов для деревьев (leaf?, empty-tree?, left-subtree & right-subtree), тогда очевидное определение будет следующим: 

(define (fold-right-tree op accum tree)
  (cond
    [(empty-tree? tree)
     accum]
    [(leaf? tree)
     (op accum tree)]
    [else (fold-right-tree op
                           (fold-right-tree op accum (right-subtree tree))
                           (left-subtree tree))]))

Преимущество в том, что оно полностьюАгностика о древовидном представлении: все, что он знает, - это имена методов доступа. В самом деле, вы можете сделать это действительно агностиком: 

(define (fold-right-tree op init tree
                         #:empty-tree? (empty? empty-tree?)
                         #:leaf? (lief? leaf?)
                         #:left-subtree (left left-subtree)
                         #:right-subtree (right right-subtree))
  (let frt ([a init] [t tree])
    (cond
      [(empty? t) a]
      [(lief? t) (op a t)]
      [else (frt (frt a (right t)) (left t))])))

Теперь он будет обходить любой тип двоичного дерева.

Вот подходящие определения для деревьев, которыефактически сделан из conses: 

;;; Tree abstraction
;;;
(define (leaf? treeish)
  (not (pair? treeish)))

(define empty-tree? null?)
(define left-subtree car)
(define right-subtree cdr)

(define cons-tree cons)
(define empty-tree '())

(define (->tree listy
                #:empty-tree (empty empty-tree)
                #:cons-tree (ctree cons-tree))
  ;; turn a cons tree into a tree
  (cond
    [(null? listy) empty]
    [(pair? listy) (ctree (->tree (car listy))
                          (->tree (cdr listy)))]
    [else listy]))
0 голосов
/ 01 ноября 2019

Из спецификации проблемы вы можете просто получить все листья дерева (с помощью функции сглаживания) и затем применить соответствующую операцию сгиба, как в: 

(define (fold-right-tree op id tree)
  (foldr op id (flatten tree)))

(fold-right-tree + 0 '((1) (2 3 4) (((5)))))  ; => 15

Это было проверено в Dr.Racket.

...