-1

順番にアクセスされたツリー（必ずしもバイナリツリーではない）のノードのリストを返そうとしています。

ツリーは、サブリストを含むリストとして表されます。たとえば、(a (b) (c (d) (e)))、b - 左サブツリー、(c (d) (e)) - 右サブツリー、a -根。結果は次のようになります: b,a,d,c,e

これは私のコードですが、常に「スタック オーバーフロー」エラーが発生するようです。誰か助けてくれませんか？

;return left-subtree
(defun left-tree(tree)
  (cond
   ((null tree) NIL)
   ((not (listp tree)) NIL)
   (t (car (cdr tree)))
  )
)

;return right-tree
(defun right-tree(tree)
  (cond
   ((null tree) NIL)
   ((not (listp tree)) NIL)
   (t (cdr (cdr tree)))
  )
)

;perform inorder
(defun inorder(tree)
  (if (not (list-length tree)) 0
  (append
   (inorder (left-tree tree))
   (list (car tree))
   (inorder (right-tree tree))
  )
 )
)
4

1 に答える 1

3

無限再帰は、数値が決して false-y ではないという事実によって引き起こされます。
に置き換え(not (list-length tree))ます(null tree)。
(つまり、サイズではなく、構造を再帰します。)

これを修正すると、基本ケースの結果が原因で型エラーが発生しますinorder- それはnilではなくである必要があり0ます。

それを修正すると、別の問題が見つかります。

CL-USER> (inorder '(a (b) (c (d) (e))))
(B A (C (D) (E)))

これは正しくありません。

の結果を見ると、right-tree実際にはあなたが主張しているものではありません。

CL-USER> (right-tree '(a (b) (c (d) (e))))
((C (D) (E)))

ご覧のとおり、これは右のサブツリーではなく、右のサブツリーを含む 1 要素のリストです。
(特に、それらが正しいと確信している場合は、各関数を個別にテストすることをお勧めします。)

ルートは最初のリスト項目 ( car)、左側のサブツリーは 2 番目 ( -carの)、右側のサブツリーは 3 番目の項目( -の)であり、あなたが書いたように3番目の項目。 サブツリーを抽出する必要があります。cdrcadrcarcdrcdrcaddr

(defun right-tree(tree)
  (cond
    ((null tree) NIL)
    ((not (listp tree)) NIL)
    (t (caddr tree))))

CL-USER> (inorder '(a (b) (c (d) (e))))
(B A D C E)
于 2015-12-09T10:16:36.533 に答える