1

数日前に出くわした興味深い質問: リストから (ノード ラベル付きの) バイナリ ツリーを構築するエレガントな関数型プログラミング ソリューションはありますか?

結果として得られるツリーは左バランスである必要があります。つまり、ツリー内のノードのすべてのレベルが完全に埋められるか、最下位のノードの場合は左から右に埋められる必要があります。また、ツリーのレベル順トラバーサル (つまり、上から下、左から右) では、元のリストが得られます。

例: リスト 1,2,3,4,5 は次のようになります。

          1
    2         3
 4    5

明白な解決策は、リストを配列に変換し、0 番目の値をルートに割り当ててから、再帰的にノードに対して子に値およびnを与えることです。2n+12n+2

しかし、私は疑問に思っていました:補助配列を必要としない、より「機能的な」方法はありますか?

4

1 に答える 1

2

rsr5スキームで表現された考え

私の最初の考えは、ノードが値とツリーを取り、関数が見つかったのと同じ場所でその値をそのツリーに挿入する関数である無限ツリーに関するものです。次に、リストに対してfold2のような再帰を実行し、関数ツリーのレベルオーダートランスバーサルを実行して、連続するリスト要素に連続する関数を適用し、バイナリツリーを蓄積します。（ただし、遅延評価でのみ機能します）

少し扱いに​​くそうだったので、 ('l 'r 'l) のような関数や、どこに挿入してインデックスを付けるかを伝えることができるデータのツリーに考えを修正しました。

(define (insert-new ls-and-rs tree)
  (cond ((or (empty-tree?) (null? ls-and-rs))
         (if (and (empty-tree?) (null? ls-and-rs))
             (make-tree x emptyTree emptyTree)
             (error "insert-new can only insert at emptyree")))
        ((sybol=? (car ls-and-rs) 'l)
         (make-tree (node tree) 
                    (insert-new (cdr ls-and-rs) 
                                (left-tree tree)) 
                    (right-tree tree)))
        ((sybol=? (car ls-and-rs) 'r)
         (make-tree (node tree) 
                    (left-tree tree) 
                    (insert-new (cdr ls-and-rs) 
                                (right-tree tree))))
        (else (error "insert-new expected 'l or 'r, recieved " 
                     (car ls-and-rs))))))

次に、インデックス自体からそれを構築できることがわかりました。1 がツリーの先頭の場合のインデックス。それ以外の場合は、ノードの右分岐です。左枝さえあれば。その親のインデックスは、常に子のフロアを 2 で割ったものです。その知識から、単にインデックスを使用してインサーターまたはアクセサーを構築できます。

(define (branch-order i)
  (let loop ((i i) (accum '()))
    (cond ((i = 1) accum)
          ((odd? i) (loop (quotient i 2) (cons 'r accum)))
          (else     (loop (quotient i 2) (cons 'l accum))))))

そこからは単純な再帰です

 (define (list->tree list)
   (let loop ((list list) (i 1) (tree emptyTree))
     (cond ((null? list) tree)
           (else (loop (cdr list)
                       (+ i 1)
                       (insert-new (branch-order i) tree))))))

もちろん、最も簡単な方法は、最小深度のバイナリ ツリーを受け入れることができる場合です。深さツリーには、ノードとブランチに加えて、最小の深さがリストされます。次に、右のサブツリーの最小の深さが左のサブツリーよりも小さい場合を除き、挿入は左のサブツリーに挿入されます。

(define (list->d-tree list)
  (fold-left (flip balanced-insert) emptyTree list))

(define (balanced-insert x d-tree)
  (cond ((= 0 (d-d-tree d-tree)) 
        (mk-d-tree x emptyTree emptyTree)
       ((= 1 (- (d-d-tree d-tree) (d-d-tree (l-d-tree d-tree))))
        (mk-d-tree (n-d-tree d-tree)
                   (balanced-insert x (l-d-tree d-tree))
                   (r-d-tree d-dtree)))
      (else 
       (mk-d-tree (n-d-tree d-tree)
                  (l-d-tree d-tree)
                  (balanced-insert x (r-d-tree d-dtree))))))

(define (mk-d-tree n l r)
 (let ((d-l (d-d-tree l))
       (d-r (d-d-tree r)))
 (list n l r (+ 1 (min d-l d-r)))))
(define (n-d-tree d-tree)
 (car d-tree))
(define (l-d-tree d-tree)
 (cadr d-tree))
(define (r-d-tree d-tree)
 (caddr d-tree))
(define (d-d-tree d-tree)
 (if emptyTree? d-tree)
     0
     (cadddr d-tree)))
(define (emptyTree? tree)
       (null? tree))
(define emptyTree '())

(define (flip f)
 (lambda (a b)
   (f b a)))

TLdr; 最小深度ツリーを使用し、左端の最小深度に挿入します。

于 2015-12-24T23:14:10.980 に答える