# 2.66

## 练习 2.66 假设记录的集合采用二叉树实现，按照其中作为键值的数值排序。请实现相应的 lookup 过程。

(define entry car)

(define (quotient n m)
(floor (/ n m))
)

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

(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
)
)
)
)
)
)
)
)

(define (tree->list tree)
(if (null? tree)
'()
(append
(tree->list (left-branch tree))
(cons
(entry tree)
(tree->list (right-branch tree))
)
)
)
)

(define (lookup given-key set-of-records)
(cond
(
(null? set-of-records)
false
)

(
(equal? given-key (key (entry set-of-records)))
(entry set-of-records)
)

(
(less-than? given-key (key (entry set-of-records)))
(lookup given-key (left-branch set-of-records))
)

(
else
(lookup given-key (right-branch set-of-records))
)
)
)

(define (key record) record)

(lookup 5 (list->tree (list 1 2 3 4 5 6 7 8 9 10)))