2

このツリーを表す (A (B (CD)) (E (F))) のようなリストがあります。

      A
    /  \
  B      E
 / \    /
C   D  F

(ABECDF) として印刷するにはどうすればよいですか?

これは私が管理した限りです：

((lambda(tree) (loop for ele in tree do (print ele))) my-list)

しかし、それは印刷します：

A
(B (C D))
(E (F))
NIL

私は Common LISP にかなり慣れていないので、使用すべき関数があるかもしれません。その場合は、私を啓発します。

ありがとう。

4

3 に答える 3

5

質問を額面通りに受け取ると、標準の深さ優先の順序付けのいずれかを使用するのではなく、「幅優先」の順序でノードを出力する必要があります。注文'。

  • 順序: CBDAEF
  • 予約注文: ABCDEF

  • ポストオーダー: CDBFEA

  • 要求された注文: ABECDF

ツリー構造では、各要素はアトム、1 つの要素を持つリスト、または 2 つの要素を持つリストのいずれかになります。リストの最初の要素は常にアトムです。

疑似コードが次のように見える必要があると私が思うのは、おおよそ次のとおりです。

Given a list 'remains-of-tree':
    Create empty 'next-level' list
    Foreach item in `remains-of-tree`
        Print the CAR of `remains-of-tree`
        If the CDR of `remains-of-tree` is not empty
             CONS the first item onto 'next-level'
             If there is a second item, CONS that onto `next-level`
    Recurse, passing `next-level` as argument.

クリーンアップできることは 100% 確信しています (他のすべてを除けば、些細な末尾再帰のように見えます)。しかし、私はそれがうまくいくと思います。

Start: (A (B (C D)) (E (F)))
Level 1:
Print CAR: A
Add (B (C D)) to next-level: ((B (C D)))
Add (E (F)) to next-level: ((B (C D)) (E (F)))
Pass ((B (C D) (E (F))) to level 2:
Level 2:
Item 1 is (B (C D))
Print CAR: B
Push C to next-level: (C)
Push D to next-level: (C D)
Item 2 is (E (F))
Print CAR: E
Push F to next-level: (C D F)
Pass (C D F) to level 3:
Level 3:
Item 1 is C
Print CAR: C
Item 2 is D
Print CAR: D
Item 3 is F
Print CAR: F
于 2008-12-21T17:46:22.383 に答える
2

リストを表現する方法に一貫性がないようです。あなたの例では、次のようになっていると思います(A ((B (C D)) (E (F))))。このように、ノードは一貫してリーフまたはリストのいずれかであり、車はリーフであり、cadrは子ノードです。

この間違いのため、これは宿題ではないと思います。これが再帰的な解決策です。

(defun by-levels (ts)
  (if (null ts)
      '()
      (append
       (mapcar #'(lambda (x) (if (listp x) (car x) x)) ts)
       (by-levels (mapcan #'(lambda (x) (if (listp x) (cadr x) '())) ts)))))

by-levelsノードのリストを取得し、最上位ノードの値を収集し、次のノードとして使用する次の子を再帰的に見つけます。

今、

(defun leafs-of-tree-by-levels (tree)
  (by-levels (list tree)))

(leafs-of-tree-by-levels '(a ((b (c d)) (e (f)))))
; (A B E C D F)

それが理にかなっていることを願っています。

于 2008-12-21T15:41:40.060 に答える
1

私のLispは少し錆びていますが、ジョナサンが示唆したように、幅優先のツリーウォークでそれを行う必要があります-これらの線に沿った何か

編集：私は前に少し早すぎて問題を読んだと思います。あなたが持っているのは基本的に関数適用の構文木なので、ここに改訂されたコードがあります。問題の説明から、CとDがBの子である場合、（B（C）（D））と書くつもりだったと思います。

; q is a queue of function calls to print
(setq q (list the-original-expression))
; for each function call
(while q
  ; dequeue the first one
  (setq a (car q) q (cdr q))
  ; print the name of the function
  (print (car a))
  ; append its arguments to the queue to be printed
  (setq q (append q)(cdr a))
  )

これが歴史です：

         q: ( (A (B (C)(D))(E (F))) )
print: A
         q: ( (B (C)(D))(E (F)) )
print: B
         q: ( (E (F))(C)(D) )
print: E
         q: ( (C)(D)(F) )
print: C
         q: ( (D)(F) )
print: D
         q: ( (F) )
print: F
         q: nil
于 2008-12-21T18:11:52.457 に答える