1 
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right) (list entry left right))

(define (mktree order items_list)
  (cond ((= (length items_list) 1)
         (make-tree (car items_list) '() '()))
        (else 
         (insert2 order (car items_list) (mktree order (cdr items_list))))))

(define (insert2 order x t)
  (cond ((null? t) (make-tree x '() '()))
      ((order x  (entry t))
       (make-tree (entry t) (insert2 order x (left-branch t)) (right-branch t)))
      ((order  (entry t) x )
       (make-tree (entry t) (left-branch t) (insert2 order x (right-branch t))))
      (else t)))

結果は次のとおりです。

(mktree (lambda (x y) (< x y)) (list 7 3 5 1 9 11))
(11 (9 (1 () (5 (3 () ()) (7 () ()))) ()) ())

しかし、私は取得しようとしています:

(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

問題はどこだ？

4

2 に答える 2

2

ここで、これを試してください：

(define (mktree order lst)
  (let loop ((lst  lst)
             (tree '()))
    (if (null? lst)
        tree
        (loop (cdr lst) (insert order (car lst) tree)))))

(define (insert order ele tree)
  (cond ((null? tree)
         (make-tree ele '() '()))
        ((order ele (entry tree))
         (make-tree (entry tree)
                    (insert order ele (left-branch tree))
                    (right-branch tree)))
        ((order (entry tree) ele)
         (make-tree (entry tree)
                    (left-branch tree)
                    (insert order ele (right-branch tree))))
        (else tree)))

期待どおりに機能します。

(mktree < '(7 3 5 1 9 11)) 
> '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

手順は問題ありませんinsert2が、mktree手順はリスト全体の反復として表現する必要があります。アキュムレータは、これまでに挿入された要素を含むツリーを追跡します。これには2つの効果があります。

  1. mktree現在、末尾再帰であり、
  2. リスト内の要素の反復順序が逆になります

特に最後のものはあなたの問題を解決します：あなたの解決策が二分木を生成するとしても、順序プロパティはあなたが期待したものと逆になります。入力リストを逆にしても機能することに注意してください。

于 2012-08-28T01:24:23.837 に答える
0

Oscar Lopez からの回答は正しいです。insert2 関数呼び出しの再帰的な性質のため、最初に S 式を完全に展開してから、リストの最後の 2 つの要素から評価を開始します (あなたの場合は 9 と 11)。 ...これの証拠として、逆の順序でリストに入れると、正しい結果が得られることがわかります。

(mktree (lambda (x y) (< x y)) (list 11 9 1 5 3 7))

(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

于 2012-08-28T20:22:22.737 に答える