1

私は、ツリーを取得し、ランダムにブランチ（左または右）を選択して、それらの値をリストに返すプログラムを作成しています。何らかの理由で機能していません。何か助けはありますか？

例：

~(rand-walk (tree 1 (leaf 2) (leaf 3)))
(1 2)

これは私がこれまでに持っているものです：

(define (rand-walk tr)
 (if (empty-tree? tr) '()
   (if (leaf? tr) tr
      (if (equal? (random 1) 0)
              (cons ((root-value tr)(root-value (left-subtree tr))) '())
              (cons ((root-value tr)(root-value (right-subtree tr))) '())))))
4

3 に答える 3

1

免責事項：私はSchemeで書いたことがありませんが、約15年前にLISPと簡単に出会いました=）

再帰的な部分は再帰的ではありません。rand-walkサブツリーを呼び出して、それを実行する必要がありますcons。

          (cons ((root-value tr)(rand-walk (left-subtree tr))) '())
          (cons ((root-value tr)(rand-walk (right-subtree tr))) '())))))
于 2013-03-27T00:56:22.330 に答える
1

それをトラバースしたい場合は、葉に到達したときにリストを返す必要があります。

(if (leaf? tr) (cons tr '())

そして、再帰的な手順ではcons、再帰的な呼び出しを行う必要があります。

(cons (root-value tr) (rand-walk (left-subtree tr)))
于 2013-03-27T00:58:06.073 に答える
1

コードに多くの問題があります。適切な実装は次のとおりです。

(define (rand-walk tr)
 (cond ((empty-tree? tr) '())
       ((leaf? tr) (list (root-value tr)))
       ((equal? (random 1) 0)
        (cons (root-value tr) (rand-walk (left-subtree tr))))
       (else
        (cons (root-value tr) (rand-walk (right-subtree tr))))))

これを書いている場合、末尾再帰アプローチを次のように使用します。

(define (rand-walk tr)
  (assert (not (empty-tree? tr)))
  (let walking ((l '()) (tr tr))
    (let ((value (root-value tr)))
      (if (leaf? tr)
          (reverse (cons value l))
          (walking (cons value l))
                   ((if (zero? (random 1)) left-subtree right-subtree) tr))))))
于 2013-03-27T01:06:30.537 に答える