SICP 2.64
quotientって何だろ?ってずっと考えてたけど、ただの割り算であることに気がついた。
(define (list->tree elements) (car (partial-tree elements (length elements)))) (define (partial-tree elts n) (if (= n 0) (cons '() elts) (let ((left-size (quotient (- n 1) 2))) (let ((left-result (partial-tree elts left-size))) (let ((left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1)))) (let ((this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size))) (let ((right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts))))))))
a
- リストを左半分と、中央と、右半分に区切る。
- 左半分と右半分をそれぞれ再帰的に左半分、中央、右半分に区切る。
- そうしてリストの要素が0になるまで3分割を続ける。
(1 3 5 7 9 11)はこういう木になる。
5 1 9 3 7 11