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