2.66

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

先复用一下前面的代码：

 
(define entry car)
(define left-branch cadr)
(define right-branch caddr)
​
(define (quotient n m) 
  (floor (/ n m))
  )
​x
 
#<undef>

 
(define (make-tree entry left right)
  (list entry left right)
  )
 
#<undef>

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