2

リストから二分探索木に要素を挿入する方法を知りたいです。次のコードが期待どおりに機能しないのはなぜでしょうか。出力は'((4 1 5 13 6) () ()) です。次の問題は、リスト内の要素をソートすることですが、今のところ、要素を挿入したいだけです。

私の出力は、私が述べた問題に対して正しいですか? 私のコードは次のとおりです。

( define ( make-tree value left right ) 
( list value left right ))
( define ( value tree ) ( car tree ))
( define ( left tree ) ( cadr tree ))
( define ( right tree ) ( caddr tree ))

(define (insert-list L T)
 (cond ((null? T) (make-tree L '() '()))
    ((= (car L) (value T)) T)
    ((< (car L) (value T)) (make-tree (value T)
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)
                                      (left T)
                                      (insert-list (car L) (right T))))))
4

1 に答える 1

2

このコードの問題

再帰的なコードを書くときは、通常、関数が引数として何を受け取るべきか、何を返す必要があるか、および基本ケースが何であるかを考慮することをお勧めします。

(define (insert-list L T)
 (cond
    ((null? T) (make-tree L '() '()))                                     ; case 1
    ((= (car L) (value T)) T)                                             ; case 2
    ((< (car L) (value T)) (make-tree (value T)                           ; case 3
                                      (insert-list (car L) (left T))
                                      (right T)))
    ((> (car L) (value T)) (make-tree (value T)                           ; case 4
                                      (left T)
                                      (insert-list (car L) (right T))))))

あなたの説明に基づいて、insert-list要素とツリーのリストを取り、それらの要素を次々とツリーに挿入することで得られるツリーを返すことになっています。このコードは実際にそれを行いますか? いくつかのケースがあります:

  1. ツリーが null の場合、いくつかの要素を含む新しいツリーを作成する必要がありますが、最初のケースでは、リスト全体を要素としてツリーを作成し、これを返します。これが、 のような結果が得られる理由です ((4 1 5 13 6) () ())。この基本ケースに到達し、 の結果を返しました(make-tree L '() '()))。
  2. リストの最初の要素がツリーの値である場合、リストの最初の要素を挿入するために他に何もする必要がないため、ツリーを返すのは正しいことです。ただし、残りの要素については何もしません。それは何の役にも立ちません。のようなテスト ケースがある場合(insert-list '(2 3 4) '(2 () ()))、戻り値は になることがわかります(2 () ())。
  3. (および 4.) これらの場合、 のような再帰呼び出しを行います(insert-list (car L) (left T))が、これは意味がありません。なぜなら、 の最初の引数insert-listは要素のリストであると想定されており、それを(car L)単一の要素で呼び出しているからです。(car L)ただし、をツリーの左側のサブツリーに挿入する必要があることを認識するのは正しいです(insert-element (car L) (left T))。代わりに を呼び出すだけであれば、それを正しく構築しています。ただし、その後、残りの要素についてはまだ何もしていません。

折りたたんで救出！

数値のリストを取得し、最初の数値をツリーに挿入して新しいツリーを取得しようとしている場合、次の数値をそのツリーに挿入する、というように、次の疑似コードのようなものを探しています。

tree = initial-tree
for element in list 
  tree = insert(element,tree)
return tree

この種の操作は、通常、機能的に で表されますfold。Flattening a List of Listsへの回答で折り畳みについて詳しく説明しましたが、そこには折り畳みに関する多くの情報があります。アイデアは、あなたが何かを変えたいということです

(insert-list '(4 1 5 13 6) '())

の中へ

(tree-insert (tree-insert (tree-insert (tree-insert (tree-insert '() 4) 1) 5) 13) 6)

これが左結合の折り畳みです。のこの定義を使用しましょうfoldl:

(define (foldl fn init list)
  (if (null? list)
      init
      (foldl fn (fn init (car list)) (cdr list))))

この特定のケースでtree-insertは、ツリーを受け取り、要素が新しいツリーを返す通常の関数を実装する必要があります。その後、リストからすべての要素を挿入する関数は単純です。

(lambda (tree elements)
  (foldl tree-insert tree elements))

例えば、

> (foldl tree-insert '() '(3 5 8 1 9))
(3 (1 () ()) (5 () (8 () (9 () ()))))
> (foldl tree-insert '() '(5 8 2 3 1 6 9))
(5 (2 (1 () ()) (3 () ())) (8 (6 () ()) (9 () ())))
> (foldl tree-insert '() '(4 1 5 13 6))             ; the test from the question
(4 (1 () ()) (5 () (13 (6 () ()) ())))
于 2013-10-15T21:12:33.933 に答える