2010数据结构实验指导书48

template <typename Comparable> class BinarySearchTree {

const Comparable & findMin( ) const; const Comparable & findMax( ) const;

bool contains( const Comparable & x ) const; void insert( const Comparable & x ); void remove( const Comparable & x ); };

现在要添加一个类模版参数Key，以及根据Key来查找和删除的函数find和remove： template <typename Key, typename Comparable> class BinarySearchTree {

bool find(const Key& k, Comparable &) const;

const Comparable & findMin( ) const; const Comparable & findMax( ) const;

bool contains( const Comparable & x ) const; void insert( const Comparable & x ); void remove( const Comparable & x ); void remove( const Key & x ); };

这样，就可以根据Key来对BST搜索和删除。读一下参考源码（或教科书pp.126-34），就知道还应该添加/修改相应的私有成员函数。

接下来，对MyBirds数组的数据以name为关键字（Key）建立一棵二叉搜索树（BST），如果打印这棵树，注意是不是少了什么？是什么原因，如果以ID作Key呢？建好BST后，对其作相应的查找。

【实验参考程序】

二分查找

C版教科书在p.24 Figure 2.9，相应的程序名是fig2_9.c。二分查找函数原型是： int BinarySearch ( const ElementType A[ ], ElementType X, int N );

用它只能对C的基本算术类型（整型、浮点、指针）进行搜索，要对其它构造类型搜索，需对其进行改写，其原型应该是：

int BinarySearch (const ElementType A[ ], int N, Key X, int cmp(Key, ElementType) ); 其中类型Key一般是ElementType的一个域；

C++版教科书的二分查找在p.59 Figure 2.9，源程序在Fig02_09.cpp，其原型也要修改为：

template <typename Key, typename Comparable>

int binarySearch( const vector<Comparable> & a, const Key & x );

原程序中两个对象的比较变成Comparable对象a和Key x的比较，所以你有两种选择：要么重载比较算符，要么把原函数中相应语句改为用Comparable对象的key和x比较。

cmp 是指向比较函数的指针，取代原先函数中的'>'、'<'等。与上面原型等价的是

int BinarySearch (const ElementType A[], int N, Key X, int (*cmp)(Key, ElementType) );