Как сложить древовидную конструкцию в ракетку? - PullRequest
Новая
       97

Как сложить древовидную конструкцию в ракетку?

1 голос
/ 09 мая 2020

У меня есть структура, которая может создавать древовидную структуру:

(struct node (value left middle right))

и другая структура, определяющая листовой узел:

(struct emptyNode ())

Как мне создать функцию, которая сворачивает дерево в одно значение, суммируя значения вместе, начиная с левого поддерева, затем из середины, затем справа?

Я думал преобразовать дерево в список , сначала в порядке левого поддерева, затем среднего, затем правого поддерева, а затем выполняя свертку по списку, но я не уверен, как его sh завершить, или если это правильный подход: 

(define (treeToList tree)
  (cond
    [(node? tree) (append (node-left tree)) (treeToList (node-left tree))
                  (append (node-middle tree)) (treeToList (node-middle tree))
                  (append (node-right tree)) (treeToList (node-right tree))]
    [else ] ;do nothing, leaf node
    ))

Ответы [ 2 ]

4 голосов
/ 09 мая 2020

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

  • текущий узел;
  • текущая повестка дня узлов, на которые она должна смотреть;
  • промежуточный итог;

И затем он решает, что делать, на основе сопоставления этих аргументов с шаблоном, перебирая узлы и выталкивая и выталкивая вещи из повестки дня.

* 1012 1013 * и empty-node, а также образец дерева, составленный из них следующим образом: 
(struct node (value left middle right))
(struct empty-node ())

(define sample-tree
  (node 1
        (node 2
              (empty-node)
              (node 3 (empty-node) (empty-node) (empty-node))
              (node -1
                    (node 1 (empty-node) (empty-node) (empty-node))
                    (empty-node)
                    (empty-node)))
        (node 10 (empty-node) (empty-node) (empty-node))
        (empty-node)))

Мы можем написать функцию для суммирования дерева следующим образом: 

(define (sum-node-tree node-tree)
  (define/match (snt-loop thing agenda sum)
    [((empty-node) '() s)
     ;; an empty node, nothing on the agenda: we're done
     s]
    [((empty-node) (cons next more) s)
     ;; an empty node, but there is an agenda, so start on the next agenda
     ;; item
     (snt-loop next more s)]
    [((node (? number? v) l m r) a s)
     ;; a node with a value: sum the value into the total, push the middle
     ;; and right children onto the agenda, and start on the left child.
     (snt-loop l (list* m r a) (+ s v))]
    [(_ _ _)
     ;; something bad in the tree
     (error 'sum-node-tree "bogus tree")])
  (snt-loop node-tree '() 0))

затем 

> (sum-node-tree sample-tree)
16
1 голос
/ 04 июня 2020

Вы можете использовать для этого пакет data / lazytree , в частности интерфейс tree-fold .

Используя пример дерева в ответе @ tfb (с именем sample-tree), мы сначала определяем функцию для получения дочерних узлов узла: 

(define (node-children t)
  (list (node-left t)
        (node-middle t)
        (node-right t)))

Затем используем ее для создания представления дерева: 

(require data/lazytree)
(define t (make-tree node-children
                     sample-tree
                     #:with-data node-value
                     #:empty-pred empty-node?))

И используйте складку дерева, чтобы получить результат: 

(tree-fold + t)
=> 16
...