Racket Tree Travesal

Question

У меня есть следующая проблема с ракеткой.

Я пытаюсь реализовать предварительный порядок дерева, обратный порядок для общего дерева.

Определение структуры:

(define-struct eempty [])
(define-struct branch [left value right])

Я не могу использовать оператор unless/when, просто if и cond. Я не могу придумать решение. Я посмотрел на псевдокод википедии, но он не очень помогает из-за парадигмы ракетного программирования.

(define (inorder tree x)
  (cond [(and (branch? tree) (branch? (branch-left tree))) (inorder (branch-left tree) x)]
        [(and (branch? tree) (branch? (branch-right tree))) (inorder (branch-right tree) x)]

Это то, что я делал до сих пор, но возникают проблемы при сопоставлении empty структуры.

Обновление:

То, что я пытаюсь сделать, это отображать / печатать значение узла в порядке или / и после заказа.

Я знаю, что должен (как-то) реализовать еще 2 условия:

(and (branch? tree) (empty? (branch-left tree))) do-something x)
(and (branch? tree) (empty? (branch-right tree))) do-something x)

Что я должен делать в чем-то? Я думаю, что я упускаю этот момент.

Любая помощь?

Answer 1

Начнем с того, что имеем:

#lang racket
(define-struct empty [])                     ; no fields
(define-struct branch [left value right])    ; three fields

Мы можем попытаться сделать несколько деревьев:

(define t1 (empty))
(define t2 (branch t1 7 t1))

Теперь мы можем немного поиграть с ним:

> t2
#<branch>
> (branch-left t2)
#<empty>
> (branch-left t1)
<i>branch-left: contract violation
  expected: branch?
  given: #<empty></i>
> (branch? t2)
#t
> (branch? t1)
#f
> (empty? t2)
#f
> (empty? t1)
#t
>

Итак , что - наш репертуар. Макрос Racket struct определяет различные функции, которые мы должны использовать - конструкторы, методы доступа, предикаты, ....

Как напечатать значение? Скажем,

(define (display-value v)
  (display #\ )
  (display v))

Так что теперь мы можем

> (display-value (branch-value t2))
 7

empty не имеет value поля, только branch имеет:

(define (display-tree-inorder t)
    (cond
        ((empty? t)
           (display-empty) )                       ; define it later
        ((branch? t)
           (display-branch-inorder                 ; define it later
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

При определении этого мы следовали за типом : наши деревья либо empty, либо branch. Это является как мы определили их, с этими двумя определениями структуры.

Осталось заполнить недостающие определения для display-empty и display-branch-inorder.

Но прежде чем мы это сделаем, у нас также может быть

(define (display-tree-preorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-preorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

(define (display-tree-postorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-postorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

Так что же делает display-empty? Ничего не делает:

(define (display-empty)
    #f)

А как насчет display-branch-inorder?

(define (display-branch-inorder lt val rt)

в соответствии с Википедией, я уверен, она начинается с отображения ее left поддерева ,

    (display-tree-inorder .... ) 

затем он отображает значение

    (display-value .... )

и завершается отображением правого поддерева:

    .... )

То же самое для двух других вариантов.

После того, как вы все это сделаете, вы почувствуете необходимость абстрагироваться и обобщить, следуя принципу разделения интересов. Хорошо. Наш display-tree-inorder объединяет несколько вещей: он пересекает дерево в соответствии с тем или иным понятием порядка и что-то делает со значением каждого узла. Все это можно абстрагировать и превратить в аргументы для обобщенной процедуры, скажем, traverse-tree.

Итак, вы видите, это довольно просто: следуйте за типами! и все будет в порядке для вас.

Answer 2

Похоже, вы пропустили ветку 'cond' для структуры 'empty'. Вы можете обратиться к учебнику Как проектировать программы для получения справки по этому вопросу, в частности, к шагу «шаблона», связанному со смешанными самоссылочными данными.