BST печать без мутаций? - PullRequest
Новая
       22

BST печать без мутаций?

0 голосов
/ 01 марта 2012

Так что я в основном хочу printbst's .. вот немного подробнее

Предоставляет функцию (printbst t), которая печатает BST, созданный из BST, как предоставлено bst.rkt в следующем формате:

-Каждый узел в BST должен быть напечатан в отдельной строке;

- левое поддерево должно быть напечатано после корня;

-Правое поддерево должно быть напечатано перед корнем;

-Ключевое значение должно иметь отступ в 2d пробелах, где d - его глубина или расстояние от корня. То есть корень не должен иметь отступ, ключи в его поддеревьях должны иметь 2 пробела, ключи в их поддеревьях 4 пробела и т. Д.

Например, полное дерево, содержащее {1,2,3,4,5,6}, будет напечатано так: 

  6
    5
4
    3
  2
    1

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

Вот что у меня есть: 

#lang racket
;;Note: struct-out exports all functions associated with the structure
(provide (struct-out BST))


(define-struct BST (key left right) #:transparent)

(define (depth key bst)
  (cond
    [(or (empty? bst) (= key (BST-key bst))) 0]
    [else (+ 1 (depth key (BST-right bst)) (depth key (BST-left bst)))]))

(define (indent int)
  (cond
    [(= int 0) ""]
    [else "  " (indent (sub1 int))]))

(define (printbst t)
  (cond
    [(empty? t) (newline)]
    [(and (empty? (BST-right t)) (empty? (BST-left t))) 
     (printf "~a~a" (indent (depth (BST-key t) t)) (BST-key t))]))

Мой printbst только печатает дерево с одним узлом, ты ... У меня есть идея, но она связана с мутацией, которую я не могу использовать :( ..... Любые предложения? Должен ли я изменить свой подход к проблеме все вместе?

1 Ответ

1 голос
/ 01 марта 2012

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

С другой стороны, мне нравится ваша функция отступа:)

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

...

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

6
5
4
3
2
1

Обновление этой программы до той, которая обрабатывает отступ, - это просто вопрос передачи одного дополнительного фрагмента информации.

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

...