Lisp - Проблемы с поступорядочением бинарного дерева

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

(defun bin-tree-postorder (b)
  "Create a list containing keys of b in postorder"
  (if (bin-tree-leaf-p b)
      (list (bin-tree-leaf-element b))
    (let
        ((elmt (bin-tree-node-element b))
         (left (bin-tree-node-left b))
         (right (bin-tree-node-right b)))
  (cons
        (append (bin-tree-postorder left)
                    (bin-tree-postorder right)) elmt))))

Однако он не запускается, потому что я получаю сообщение об ошибке:

*** - APPEND: A proper list must not end with +

Вот мой след:

1. Trace: (BIN-TREE-POSTORDER '(* (+ (2) (3)) (- (7) (8))))
2. Trace: (BIN-TREE-POSTORDER '(+ (2) (3)))
3. Trace: (BIN-TREE-POSTORDER '(2))
3. Trace: BIN-TREE-POSTORDER ==> (2)
3. Trace: (BIN-TREE-POSTORDER '(3))
3. Trace: BIN-TREE-POSTORDER ==> (3)
2. Trace: BIN-TREE-POSTORDER ==> ((2 3) . +)
2. Trace: (BIN-TREE-POSTORDER '(- (7) (8)))
3. Trace: (BIN-TREE-POSTORDER '(7))
3. Trace: BIN-TREE-POSTORDER ==> (7)
3. Trace: (BIN-TREE-POSTORDER '(8))
3. Trace: BIN-TREE-POSTORDER ==> (8)
2. Trace: BIN-TREE-POSTORDER ==> ((7 8) . -)

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

(((2 3) + (7 8) -) *)

Однако правильный ответ:

(2 3 + 7 8 - *)

Может ли кто-нибудь, кто ответит, дать подсказки или указатели вместо измененного кода, чтобы я мог лучше понять проблему? Я бы предпочел не смотреть на ответы учебника, потому что это не поможет мне понять, что я делаю неправильно.

Будьте уверены, я превращу его в хвостовую рекурсивную функцию после того, как будет выяснена основная рекурсивная функция.

Спасибо всем, кто может помочь!


lisp binary-tree common-lisp postorder
person OrangeCalx01    schedule 21.12.2015    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Учитывайте значения left, right и elmt при этих вызовах cons и append бывает:

  (cons
        (append (bin-tree-postorder left)
                    (bin-tree-postorder right)) elmt))))

bin-tree-postorder должен возвращать список, поэтому вызов append должен работать нормально. (Я знаю, что на самом деле это еще не так, но мы работаем с предположением, что рекурсивные вызовы прошли нормально.) Итак, теперь функция будет возвращать значение:

(cons <appended-postorder-results> elmt)

Теперь elmt похож на символы +. Давайте воспользуемся REPL, чтобы увидеть, что возвращает такой вызов:

CL-USER> (cons '(2 3) '+)
((2 3) . +)

Это не то, что ты хотел. Вам нужен список (2 3 +). Чтобы получить это, вы не хотите использовать минусы в elmt, потому что тогда вы получите неправильный список, подобный показанному выше. Вы можете найти точечную нотацию в схеме полезной для понимания того, что означает .. Последующие вызовы append будут жаловаться на неправильный список, как вы видели:

CL-USER> (append '((2 3) . +) '(4 5))
; Evaluation aborted on #<TYPE-ERROR expected-type: LIST datum: +>.

Аргументы append имеют требования, которые могут показаться вам необычными, если вы сами не реализовали append. В документации для append говорится:

Синтаксис:

добавить &остальные списки результатов

Аргументы и ценности:

listeach должен быть правильным списком, за исключением последнего, который может быть любым объектом.

Причина в том, что append должен пройти до конца каждого из списков (кроме списка), чтобы создать новый список, который в конечном итоге завершается (копией) следующего списка. Это означает «замену» последнего nil следующим списком. Неправильный список (например, (1 . 2) не имеет nil в конце.

Самое простое, что вы можете сделать, это просто удалить cons и добавить аргумент в append, а именно список, содержащий elmt:

(append (bin-tree-postorder left)
        (bin-tree-postorder right)
        (list elmt))
person Joshua Taylor    schedule 21.12.2015
comment
Опасно могли жить и rplacd или rplaca. :-) - person scooter me fecit; 21.12.2015

arrow_upward
2
arrow_downward

append объединяет списки вместе; element дерева не является списком. Так что либо вы не можете использовать append, либо вам нужно составить список из element.

Таким образом, второй случай можно записать как (append (bin-tree-postorder left) (bin-tree-postorder right) (list elmt)).

person Scott Hunter    schedule 21.12.2015
comment
(список elmt) в конце формы cons вместо elmt дает частично правильный ответ. Что еще я мог бы использовать вместо добавления? - person OrangeCalx01; 21.12.2015
comment
@OrangeCalx01, обратите внимание, что ответ @ScottHunter правильный, вы должны использовать (append (bin-tree-postorder left) (bin-tree-postorder right) (list elmt)), а не (cons (append (bin-tree-postorder left)(bin-tree-postorder right)) (list elmt)). Первая форма даст правильный ответ (2 3 + 7 8 - *). - person Renzo; 21.12.2015

arrow_upward
1
arrow_downward

Если вы не хотите использовать append, вы можете использовать аккумулятор для создания списка в обратном порядке. Вот код, который это делает.

(defun bin-tree-postorder (b &optional accumulator)
  (if (bin-tree-leaf-p b)
      (cons (bin-tree-leaf-element b) accumulator)
      (bin-tree-postorder (bin-tree-node-left b)
                          (bin-tree-postorder (bin-tree-node-right b)
                                              (cons (bin-tree-node-element b)
                                                    accumulator)))))

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

person malisper    schedule 21.12.2015

arrow_upward
-1
arrow_downward

push это то, что вы ищете - поместите новые элементы в конец списка. reverse при необходимости после завершения.

person scooter me fecit    schedule 21.12.2015
comment
Кто-то хочет объяснить, почему push невозможен вариант? - person scooter me fecit; 21.12.2015