Сгиб дерева в Racket

Question

Я новичок в Racket и получил такой вопрос:

• определить структуру, node, которая имеет следующие поля: value, left, middle, right. Эта структура представляет узлы в древовидной структуре.
  Эти поля содержат значение, хранящееся в узле, левом поддереве, среднем поддереве и правом поддереве соответственно. Если поддерево не существует, то соответствующее поле должно содержать, emptyNodeкак описано ниже.
• определить структуру, emptyNodeчтобы указать пустой узел в дереве.
• Напишите функцию, treeFoldкоторая принимает функцию f,, начальное значение initial, и древовидную структуру tree, как параметры. Затем он должен произвести одно значение , которое является результатом использования fсложить значения в дереве ( с использованием left, middleи rightподдеревьев в таком порядке). Обратите внимание, что fэто функция, которая принимает два параметра. Первый параметр - это значение из дерева, а второй - частично накопленный результат.

вызов функции должен быть:

(treeFold (lambda (a acc) (+ a acc)) 15 tree) 

дерево:

(node 7 (node 5 (emptyNode) (emptyNode) (emptyNode)) 
        (node 20 (emptyNode) (emptyNode) (emptyNode)) 
        (emptyNode))

выход : 47

вот что я сделал до сих пор:

(struct node (value left middle right) #:transparent)

(struct emptyNode () #:transparent)

(define tree 
    (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))

(define (treeFold f initial tree)
  (if (emptyNode? tree)
     (emptyNode)
     (node (f initial (node-value tree))
           (node-left tree)
           (node-middle tree)
           (node-right tree))))

Как я могу получить общее количество листьев?

любые идеи или помощь, спасибо

---

edit: Итак, на основе ответа и обсуждения в его комментариях я получил новую функцию, но все еще есть ошибка, и я не мог ее найти. вот:

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree) 
             (f (treeFold f 
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

подскажите, пожалуйста, как это исправить? благодарю вас.

---

изменить: окончательный код

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) (f initial 0)] 
    [else (f  (node-value tree)                
              (treeFold f                   
                   (treeFold f 
                        (treeFold f initial 
                             (node-left tree)) 
                             (node-middle tree)) 
                             (node-right tree)))]))

это работает как я ожидал

Answer 1

обновление после того, как вопрос был отредактирован новой версией функции.

Это шаг в правильном направлении. В нем есть несколько правильных частей и несколько неправильных.

Функции подобны коробкам, которые можно соединить вместе. По одним проводам материал входит, по другим - уходит. У каждой коробки есть свой правильный способ использования: количество проводов и материал, который ожидается в них втекать.

Ваша новая версия:

(define (treeFold f initial tree) 
  (cond 
    [(emptyNode? tree) 
          (f initial 0)] 
    [else (f (node-value tree)                 ;; (1)
             (f (treeFold f                    ;; (2)
                   (treeFold f 
                      (treeFold f initial 
                         (node-left tree)) 
                      (node-middle tree)) 
                    (node-right tree))))]))

fожидает двух аргументов. (f initial 0) выглядит правильно, по крайней мере, в этом отношении. Звонок (1)тоже. Но вызов fat (2)имеет только один аргумент f, поэтому не может быть правильным.

Далее, к его значению. Три вложенные вызовы treeFoldявляются почти правы: мы «идти» в (node-left tree), то есть левое поддерево, с в initialкачестве начального значения, то мы получим результат от этого и использовать его в качестве нового начального значения для перехода в средний суб -дерево и используйте вычисленный результат, чтобы пройти по правому поддереву. Ницца. Мы закончили . Это конечный результат, который нам нужен - не нужно его fвводить дальше. Таким образом, эти два вызова fвыше трех вложенных вызовов для treeFoldвообще не нужны.

Кроме того, что нам делать с (node-value tree)? Куда это подходит? Ответ, он должен быть объединен с initialзначением, путем вызова f, и результат в том , что следует использовать в качестве начального значения , с которым мы идем над левым поддерево; значение, с которого мы начинаем сворачивание.

Базовый вариант также неверен. У нас уже есть initial, зачем нам 0вдруг его объединять ? А почему 0? Мы могли бы , например, складывать дерево, удерживая строки , и объединение строк с числом 0не имело бы большого смысла.

Нет, 0будет предоставлено как начальное значение при вызове treeFold, например

(define (sumAllNumbersInWholeTree tree)
  (treeFold + 0 tree))

А с деревом, содержащим строки, мы могли бы, например, определить

(define (collectAllStringsInWholeTree tree)
  (treeFold string-append "" tree))

Далее следует первоначальный вариант ответа. Просмотрите его (очень немного отредактированный) пример с вашим новым пониманием. :)

---

За

(define tree 
    (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))

это должно быть, согласно спецификации,

47 == (treeFold + 15 tree)
   == (treeFold + 15 
        (node 7 
          (node 5 (emptyNode) (emptyNode) (emptyNode)) 
          (node 20 (emptyNode) (emptyNode) (emptyNode)) 
          (emptyNode)))
   == (treeFold + 
          (treeFold + 
              (treeFold + (+ 15 7) (node 5 (emptyNode) (emptyNode) (emptyNode)))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold +  
                   (treeFold + 
                       (treeFold + (+ 22 5) (emptyNode))
                       (emptyNode))
                   (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold +  
                   (treeFold + 27 (emptyNode))
                   (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 
              (treeFold + 27 (emptyNode))
              (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   == (treeFold + 
          (treeFold + 27 (node 20 (emptyNode) (emptyNode) (emptyNode)))
          (emptyNode))
   .........

(пишем ==для «равных»). Это уже дает вам все необходимое для полного определения, а именно:

(treeFold + i (node v lt md rt))
==
(treeFold +
   (treeFold +
      (treeFold + (+ i v) lt)
      md)
   rt)

и

(treeFold + i (emptyNode))
==
i