1

ヘルパー関数を次のように定義しました。

;; returns value of node
(define (value node)
  (if (null? node) '()
      (car node)))

;; returns left subtree of node
(define (left node)
  (if (null? node) '()
      (cadr node)))

;; returns right subtree of node
(define (right node)
  (if (null? node) '()
      (caddr node)))

leavesそして、ツリーの葉のリストを左から右の順に返す関数を作成しようとしています。

(define (leaves tree)
    (if (and (?null (left tree)) (?null (right tree)))
        ???
        (leaves (left tree)) (leaves (right tree))))

しかし、それは私が得ることができる限りです

例:(葉'（1（2（）（））（3（）（））））は'（2 3）と評価する必要があります

4

3 に答える 3

1

これは、幅優先探索を実行しているように見えますが、子が2つある場合は自分で印刷しない（子が1つしかないノードを印刷したくない場合は1つだけ）という変更が加えられています。

私は最初にそれを解決し、次にこの問題を解決するためにあなたの解決策をそれに変更することを目指します。

于 2012-10-05T19:23:22.137 に答える
1

これまでのところ、???葉の値を評価する必要があります。(value node)それはあなたのイテレーションの基本ケースだからです。また、反復ケースでベースケースから取得した値を組み合わせる必要があります。 list通常、複数の結果を組み合わせる必要がある場合に最初に試すのは良い候補ですがcons、通常は2回目の試みです。これらの提案を取り入れると、leaves関数は次のようになります。

(define (leaves tree)
    (if (and (null? (left tree)) (null? (right tree)))
        (value tree)
        (list (leaves (left tree)) (leaves (right tree)))))

これは、のサンプルで実行すると、(leaves '(1 (2 () ()) (3 () ())))実際にに評価され(2 3)ます。

でも; あなたは終わっていない！1レベルの再帰でのみテストしています。もっと大きな木を作ったらどうなるでしょうか？のようなもの：(leaves '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())))) これを実行すると、が得られ((4 5) (6 7))ます。これらは正しい順序で正しい値ですが、構造が多すぎて、括弧が多すぎます。これは、スキームのキャリアを通じて遭遇する典型的な問題です。そのため、なぜそれが発生するのか、そしてどのように問題に取り組むことができるのかを説明しましょう。

ifフォームの2つのブランチを見ると(value tree)、アトム、この場合は数値を返すことがわかります。elseブランチはの2つを取り、???それをのリストに変換します???。elseブランチを複数回実行します-基本ケースでないときはいつでも。これは、ラップ、ラップ、およびラップを継続して、より深いリスト構造にすることを意味します。それで、これが私たちがそれについてすることです。

基本ケースでリストを返し、再帰ケースでリストをフラットに保ちましょう。(list (value tree))基本ケースでリストを返すには、単に。を返す​​のではなく、返すのと同じくらい簡単(value tree)です。再帰の場合、2つのリストを取得し、より深いリストを作成せずにそれらを組み合わせる関数が必要です。そのような関数は存在します- append。leavesそれでは、関数がどのように見えるかを見てみましょう。

(define (leaves tree)
        (if (and (null? (left tree)) (null? (right tree)))
            (list (value tree))
            (append (leaves (left tree)) (leaves (right tree)))))

Intermezzo-テストケース

Racketには、 rackunitと呼ばれる参入障壁が非常に低いテストスイートライブラリがあります。ファイルの最後にいくつかの簡単なテストケースをまとめましょう。

(require rackunit)
;;empty tree
(check-equal? (leaves '()) '())

;;simple balanced tree
(check-equal?
 (leaves '(1 (2 () ()) (3 () ())))
 '(2 3))

;;larger balanced tree
(check-equal?
 (leaves '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ()))))
 '(4 5 6 7))

;;unbalanced tree
(check-equal?
 (leaves '(1 (2 (4 () ()) ()) (3 () ())))
 '(4 3))

最近、ラケットはサブモジュールのサポートを追加し、興味があり、それらを調べたい場合は、テストサブモジュールの特定のサポートを追加しました。

葉の問題に戻りましょう。テストを実行すると、関数が不均衡なツリーで適切に動作しないことがわかります。()リーフが1つしかないノードがある場合、余分なsを取得します。これは、リーフではないノードにいるときは常に、左と右の両方のサブツリーをトラバースしているためです。私たちが本当に必要としているのは、私たちのさらに2つのケースifです。sをネストすることもできますifが、スキームのcond形式の方が理にかなっています。

さて、私たちが記入しようとしているテンプレートは次のとおりです。

(define (leaves tree)
  (cond [(leaf? tree) (...)]
    [(and (has-left? tree) (has-right? tree)) 
     (...)]
    [(has-left? tree) (...)]
    [(has-right? tree) (...)]
    [else (error "should never get here")]))

これが宿題である場合はそこで停止し、残りの方法でこれを理解して解決する満足感を与えます。私の説明が、「ここにコードがあります」という答えよりも多くの方向性を与えてくれることを願っています。

于 2012-10-08T15:26:52.793 に答える
0 
(define (list-of-leaves tree)
  (if(leaf? tree)
     (list (node tree))
     (cond((right-branch-only? tree)(list-of-leaves (right-branch tree)))
          ((left-branch-only? tree)(list-of-leaves (left-branch tree)))
          (else(append (list-of-leaves (left-branch tree))
                       (list-of-leaves (right-branch tree)))))))
于 2013-10-26T19:10:23.423 に答える