У меня следующая проблема с 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)
Что мне нужно делать в чем-то? Я думаю, что упускаю этот момент.
Любая помощь?
Дерево - это ветвь, левое и правое значение которой могут быть либо ветвью, либо пустым. Пример: (определить дерево (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 пусто))))
Похоже, вам не хватает ветки cond для пустой структуры. Вы можете обратиться к учебнику Как разрабатывать программы за помощью по этому вопросу, особенно к шагу «шаблона», связанному со смешанными самореферентными данными.
В частности, раздел 4.6, Проектирование с помощью детализации, который описывает, как сделать шаблон для определения данных, использующего one of
. И раздел 9, Проектирование с использованием самореференциальных определений данных помогает поместить это в контекст самореферентных данных, таких как деревья.
Вот чего мне не хватает. Я знаю, что должно быть еще два условия, т.е. (и (ветвь? Дерево) (пусто? (Ветвь-левое дерево)) и (и (ветвь? Дерево) (пусто? (Ветвь-левое дерево)). Но я не Я не понимаю, что мне делать, если эти условия верны.
Ах! Нет, вы застряли в ловушке «страха перед нулевым». Я предполагаю, что у вас есть некоторый опыт программирования, который вызывает у вас проблемы. У вас почти наверняка должна быть ветка (пустая? Дерева). Однако, чтобы лучше ответить на ваш вопрос, возможно, вы могли бы добавить к своему вопросу дополнительный контекст. Что конкретно вы пытаетесь сделать для делать при обходе до или после заказа?
Я обновил свой вопрос, добавив дополнительную информацию. Любая помощь приветствуется!
Начнем с того, что имеем:
#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
.
Итак, видите ли, это довольно просто: следите за типами! и все подойдет вам.
Спасибо большое! Это мне очень помогло!
Какой у вас определение данных для дерева? Дерево всегда ветвь? Или это может быть
one of
пустая или ветка? (Я имею в виду определение данных в контексте Как разрабатывать программы, учебника, упомянутого в ответе Джона Клементса. определение данных - это первый шаг рецепта дизайна.)