2.66

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

先复用一下前面的代码：

(define entry car)
(define left-branch cadr)
(define right-branch caddr)

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