0

ラケットにbst(二分探索木)を実装しようとしています。bst は再帰的なリスト (list x leftChild rightChild) であり、leftChild と rightChild はリストそのものです。次のコードを書きました。

(define (insert bst x)(
     (cond 
       [(null? bst) (append bst (list x '() '()))]
       [(<= x (car bst)) (insert (cadr bst) x)]
       [else (insert (caddr bst) x)]  
     )))

私が書くとき

(insert (insert null 8) 9)

エラーが発生します：関数呼び出し：開き括弧の後に関数が必要ですが、受信しました（リスト8空空） 誰でもこれを説明できますか？

4

1 に答える 1

1

()報告されたエラーは、式を囲む誤ったペアがあるために発生condします。これにより、Scheme は何もないときにプロシージャを実行しようとします。しかし、それ以外にも論理的な問題がいくつかあります。要素が挿入されたときに実際にリストを構築していないこと、およびケースが欠落している場合があります - 要素がツリーに既に存在する場合はどうなりますか?. これはうまくいくはずです：

(define (insert bst x)
  (cond 
    [(null? bst)
     (list x '() '())] ; this is the correct way to handle the base case
    [(= x (car bst))   ; this case was missing
     bst]              ; simply leave the tree as it is
    [(< x (car bst))   ; if this happens, recursively build a list
     (list (car bst) (insert (cadr bst) x) (caddr bst))] 
    [else              ; if this happens, recursively build a list
     (list (car bst) (cadr bst) (insert (caddr bst) x))]))

手順の使用方法は次のとおりです。

(insert (insert (insert (insert null
                                10)
                        5)
                16)
        13)

=> '(10 (5 () ()) (16 (13 () ()) ()))
于 2013-11-08T15:23:25.283 に答える