Ракетное путешествие по дереву

У меня следующая проблема с Racket.

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

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

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

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

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

Какой у вас определение данных для дерева? Дерево всегда ветвь? Или это может быть one of пустая или ветка? (Я имею в виду определение данных в контексте Как разрабатывать программы, учебника, упомянутого в ответе Джона Клементса. определение данных - это первый шаг рецепта дизайна.)

Alex Knauth 08.09.2018 18:16

Дерево - это ветвь, левое и правое значение которой могут быть либо ветвью, либо пустым. Пример: (определить дерево (make-branch (make-branch (make-branch empty 2 empty) 4 (make-branch empty 5 empty)) 10 (make-branch (make-branch empty 12 empty) 15 (make-branch empty) 18 пусто))))

fraccaman 08.09.2018 19:05
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
3
2
403
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

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

В частности, раздел 4.6, Проектирование с помощью детализации, который описывает, как сделать шаблон для определения данных, использующего one of. И раздел 9, Проектирование с использованием самореференциальных определений данных помогает поместить это в контекст самореферентных данных, таких как деревья.

Alex Knauth 08.09.2018 00:02

Вот чего мне не хватает. Я знаю, что должно быть еще два условия, т.е. (и (ветвь? Дерево) (пусто? (Ветвь-левое дерево)) и (и (ветвь? Дерево) (пусто? (Ветвь-левое дерево)). Но я не Я не понимаю, что мне делать, если эти условия верны.

fraccaman 08.09.2018 01:04

Ах! Нет, вы застряли в ловушке «страха перед нулевым». Я предполагаю, что у вас есть некоторый опыт программирования, который вызывает у вас проблемы. У вас почти наверняка должна быть ветка (пустая? Дерева). Однако, чтобы лучше ответить на ваш вопрос, возможно, вы могли бы добавить к своему вопросу дополнительный контекст. Что конкретно вы пытаетесь сделать для делать при обходе до или после заказа?

John Clements 08.09.2018 16:51

Я обновил свой вопрос, добавив дополнительную информацию. Любая помощь приветствуется!

fraccaman 08.09.2018 17:12
Ответ принят как подходящий

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

#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)
branch-left: contract violation
  expected: branch?
  given: #<empty>
> (branch? t2)
#t
> (branch? t1)
#f
> (empty? t2)
#f
> (empty? t1)
#t
>

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

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

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

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

    (display-tree-inorder .... ) 

тогда он должен отображать свое значение

    (display-value .... )

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

    .... )

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

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

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

Спасибо большое! Это мне очень помогло!

fraccaman 10.09.2018 12:03

Другие вопросы по теме