2

(+ 1 (* 2 (- 3 5))) のような算術式が、以下のように葉に数字があり、内部ノードに演算子記号があるツリーのような構造と考えられていると想像してください。

     +
   /   \
  1     *
       /  \
      2    -
          /  \
         3    5

ツリーの特定の部分にアクセスするために、これらの関数が既に定義されています。

;; returns tree node
(define (operator lst)
  (cadr lst))

;; returns left tree
(define (left-op lst)
  (car lst))

;; returns right tree
(define (right-op lst)
  (cddr lst))

私は 3 つの関数preorder、inorder、およびを記述しようとしています。これらの関数は、postorder遭遇した順序でトラバースされたツリーのリストを返します。

以前の Java プログラミングからツリー トラバーサルがどのように機能するかは知っていますが、これをコーディングするのに問題があります。

上記の例： (preorder '(+ 1 (* 2 (- 3 5))))=>(+ 1 * 2 - 3 5)

4

1 に答える 1

2

ツリーの実装は完全に正しくありません。リーフ (例では数値) を、NULL の左右のサブツリーを持つ別のツリーとして表す必要があります。また、make-tree「コンストラクタ」があると便利です。ステップバイステップで進みましょう - まず、ツリーを表現するための正しい抽象化:

(define (make-tree value left right)
  (list left value right))

(define (operator tree)
  (cadr tree))

(define (left-op tree)
  (car tree))

(define (right-op tree)
  (caddr tree))

では、トラバーサルについてです。最初の 1 つをお手伝いしますpreorder。

(define (preorder tree)
  (if (null? tree)
      '()
      (append (list (operator tree))
              (preorder (left-op tree))
              (preorder (right-op tree)))))

問題のツリーは次のようになります。

(define tree
  (make-tree '+
             (make-tree 1 '() '())
             (make-tree '*
                        (make-tree 2 '() '())
                        (make-tree '-
                                   (make-tree 3 '() '())
                                   (make-tree 5 '() '())))))

次のように使用します。

(preorder tree)
> '(+ 1 * 2 - 3 5)

他の 2 つのトラバーサルは非常によく似ています。3 つの引数をappendケースごとに正しい順序に並べ替えるだけです。これは読者の演習として行います。

于 2012-10-12T01:18:26.727 に答える