Блог

Я новичок в ракетке, и у меня возник этот вопрос:

• определите структуру, 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))))
  

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

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

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

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

  

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

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

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

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

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

 (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) также. Но вызов f at (2) имеет только один аргумент, предоставленный to 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