二叉查找树的简单模板实现

二叉排序树又称二叉查找树，是一种的高效的查找数据结构，查找效率等同二分法。

 

以下是二叉查找树的一种简单模板实现：

 

#include <iostream>
using namespace std;
template <typename T>
class BinSearchTree{
public:
typedef Node* tree;
BinSearchTree():rp(NULL), n(){}
~BinSearchTree(){
_clear();
n = 0;
}
void insert(const T& d){
_insert(rp, new Node(d));
++n;
}
int high()const{
return _high(rp);
}
tree& find(const T& d){
return _find(rp, d);
}
void travel()const{
_travel(rp);
cout << endl;
}
bool empty(){
return rp == NULL;
}
int size(){
return n;
}
const T& root(){
if(empty())
throw "empty";
return rp->data;
}
void update(const T& old_data, const T& new_data){
if(remove(old_data))
insert(new_data);
}
bool remove(const T& d){
tree& t = find(d);
if(t == NULL)
return false;
Node* p = t;
if(t->L != NULL)
insert(t->R, t->L);
t = t->R;
delete p;
--n;
return true;
}
void clear(){
_clear(rp);
}
private:
struct Node{
T data;
Node* L;
Node* R;
Node(T d):data(d), L(), R(){}
Node(T d, Node* l, Node* r):data(d), L(l), R(r){}
};
Node* rp;//root pointer
int n;//节点个数
/***************以下为工具函数，供接口方法调用**********************/
//向BST中插入节点
void _insert(tree& t, Node* p){
if(t == NULL)
t = p;
else if(p->data < t->data)
insert(t->L, p);
else
insert(t->R, p);
}
//找到对应的节点，并返回指向该节点指针的引用
Node*& _find(tree& t, const T& d){
if(t->data == d || t == NULL)
return t;
else if(d < t->data)
return _find(t->L, d);
else
return _find(t->R, d);
}
//遍历BST
void _travel(const tree& t)const{
if(t != NULL){
_travel(t->L);
cout << t->data << ' ';
_travel(t->R);
}
}
//clear BST
void _clear(tree& t){
if(t != NULL){
_clear(t->L);
_clear(t->R);
delete t;
t = NULL;
}
}
//求BST的高度
int _high(tree& t)const{
if(t == NULL)
return 0;
int lh = _high(t->L);
int rh = _high(t->R);
return 1 + ((lh > rh) ? lh : rh);
}
};
int main()
{
BinSearchTree<int> bst;
bst.insert(2);
bst.insert(6);
bst.insert(1);
bst.travel();
cout << "high:" << bst.high() << endl;
bst.update(2, 3); 
bst.travel();  
return 0;
}