练习 2.66

根据数据抽象的原则,我们完全不必了解记录集合所使用的二叉树的实现细节,只要知道对于一棵树,有以下函数可以作用于它:

  • entry :取出当前节点
  • left-branch :转向树的左分支
  • right-branch :转向树的右分支
  • key :从节点中获取键

根据以上这些函数,我们可以给出相应的二叉树实现的数据库 lookup 程序:

;;; 66-lookup.scm

(define (lookup given-key tree-of-records)
    (if (null? tree-of-records)                                             ; 数据库为空,查找失败
        #f
        (let ((entry-key (key (entry tree-of-records))))                    ; 获取当前节点的键
            (cond ((= given-key entry-key)                                  ; 对比当前节点的键和给定的查找键
                    (entry tree-of-records))                                ; 决定查找的方向
                  ((> given-key entry-key)
                    (lookup given-key (right-branch tree-of-records)))
                  ((< given-key entry-key)
                    (lookup given-key (left-branch tree-of-records)))))))

lookup 实际上就是树的包装程序了。

以下是一棵假设的树的例子(以人名记录为例):

                  (7 "John")
                  /        \
                 /          \
          (3 "Mary")       (19 "Tom")
          /     \
(1 "Peter")    (5 "Jack")

讨论

blog comments powered by Disqus