1

Lisp を楽しむために学んでいて、今までそれほど苦労したことはありませんでした。私はこのサイトの 3 回目のレクチャーに参加しています。「特定のバイナリ ツリーのメンバーをポストオーダーで含むリストを作成する関数を実装する」という演習を完了しようとしています。これまでの私のコードは次のとおりです。

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

問題をよりよく理解できるように、修正されたコードの代わりに、答えた人は誰でもヒントやポインタを提供できますか? チュートリアルの回答は見たくありません。なぜなら、それは私が間違っていることを学ぶのに役立たないからです。

基本的な再帰関数が理解できたら、末尾再帰関数に変換しますのでご安心ください。

助けてくれる人に感謝します！

4

4 に答える 4

1

を使用したくない場合は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)))))

関数が行うことは、ツリーのポスト オーダーの結果をアキュムレータに追加することです。最初に現在の要素をアキュムレータに追加し、右側のサブツリーのポスト オーダーをアキュムレータに追加し、次に左側のサブツリーのポスト オーダーをアキュムレータに追加することにより、再帰的に機能します。

于 2015-12-21T03:16:43.697 に答える
-1

push探しているものです -- 新しい要素をリストの最後にプッシュします。reverse必要に応じて。

于 2015-12-21T02:55:50.397 に答える