实现了二叉查找树的：插入，查找，获取最大、最小值，删除最大、最小值，按照给定的键值删除键值，向上取整等方法。
代码如下：
头文件如下：
/*
* BST.h
*
* Created on: 2014年6月28日
* Author: zhongchao
*/
#ifndef _BST_
#define _BST_
#include <string>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
using namespace std;
template<typename T1,typename T2>
struct Node
{
T1 _key;
T2 _value;
Node* left;
Node* right;
int n;
};
template<typename T1,typename T2>
class BST
{
private:
Node<T1, T2>* root;
public:
BST();
int size();
int size(Node<T1, T2>* node);
void add(T1 key, T2 value);
Node<T1, T2>* add(Node<T1, T2>** node, T1 key, T2 value);
T2 get(T1 key);
Node<T1, T2>* get(Node<T1, T2>* node, T1 key);
T2 min();
Node<T1, T2>* min(Node<T1, T2>* node);
T2 max();
Node<T1, T2>* max(Node<T1, T2>* node);
//删除最大值
void deleMin();
Node<T1, T2>* deleMin(Node<T1, T2>* node);
//删除最小值
void deleMax();
Node<T1, T2>* deleMax(Node<T1, T2>* node);
//删除任意值
void del(T1 key);
Node<T1, T2>* del(Node<T1, T2>* node, T1 key);
//向上取整
T1 floor(T1 key);
Node<T1, T2>* floor(Node<T1, T2>* node, T1 key);
//取第k个大小的key
T1 select(int k);
Node<T1, T2>* select(Node<T1, T2>* node, int k);
//取key值所在的排名
int rank(T1 key);
int rank(T1 key, Node<T1, T2>* node);
};
#endif /* _BST_ */
源文件
#include "BST.h"
template<typename T1, typename T2>
BST<T1, T2>::BST()
{
root = NULL;
}
template<typename T1, typename T2>
int BST<T1, T2>::size()
{
return size(root);
}
template<typename T1, typename T2>
int BST<T1, T2>::size(Node<T1, T2>* node)
{
if(node == NULL)
return 0;
else
return node->n;
}
template<typename T1,typename T2>
void BST<T1, T2>::add(T1 key, T2 value)
{
add(&root, key, value);
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::add(Node<T1, T2>** node, T1 key, T2 value)
{
if(*node == NULL)
{
(*node) = new Node<T1, T2>();
(*node)->_key = key;
(*node)->_value = value;
(*node)->n = 1;
}
if((*node)->_key < key)
{
(*node)->right = add(&((*node)->right), key, value);
}
else if((*node)->_key > key)
{
(*node)->left = add(&((*node)->left), key, value);
}
else
{
(*node)->_value = value;
}
(*node)->n = size((*node)->left) + size((*node)->right) + 1;
return *node;
}
template<typename T1, typename T2>
T2 BST<T1, T2>::get(T1 key)
{
return get(root, key)->_value;
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::get(Node<T1, T2>* node, T1 key)
{
if(node == 0)
{
return NULL;
}
if(node->_key < key)
{
return get(node->right, key);
}
else if(node->_key > key)
{
return get(node->left, key);
}
else if(node->_key == key)
{
return node;
}
}
template<typename T1, typename T2>
T2 BST<T1, T2>::min()
{
return min(root)->_value;
}
template<typename T1,typename T2>
Node<T1, T2>* BST<T1, T2>::min(Node<T1, T2>* node)
{
if(node->left == NULL)
return node;
if(node->left != NULL)
{
return min(node->left);
}
}
template<typename T1, typename T2>
T2 BST<T1, T2>::max()
{
return max(root)->_value;
}
template<typename T1,typename T2>
Node<T1, T2>* BST<T1, T2>::max(Node<T1, T2>* node)
{
if(node->right == NULL)
return node;
if(node->right != NULL)
{
return max(node->right);
}
}
template<typename T1, typename T2>
void BST<T1, T2>::deleMin()
{
root = deleMin(root);
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::deleMin(Node<T1, T2>* node)
{
if(node->left == NULL)
{
return node->right;
}
else
{
node->left = deleMin(node->left);
}
return node;
}
template<typename T1, typename T2>
void BST<T1, T2>::deleMax()
{
root = deleMax(root);
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::deleMax(Node<T1, T2>* node)
{
if(node->right == NULL)
{
return node->left;
}
else
{
node->right = deleMax(node->right);
}
return node;
}
template<typename T1, typename T2>
void BST<T1, T2>::del(T1 key)
{
del(root, key);
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::del(Node<T1, T2>* node, T1 key)
{
if(node == NULL)
return NULL;
if(node->_key == key)
{
if(node->left == NULL) return node->right;
if(node->right == NULL) return node->left;
Node<T1, T2>* t = node;
node = min(t); //获得最小值
node->right = delMin(t);
node->left = t->left;
return node;
}
else if(node->_key > key)
{
node->right = del(node->right, key);
}
else if(node->_key < key)
{
node->left = del(node->left);
}
}
template<typename T1, typename T2>
T1 BST<T1, T2>::floor(T1 key)
{
Node<T1, T2>* x = floor(root, key);
if(x == NULL) return NULL;
return x->key;
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::floor(Node<T1, T2>* node, T1 key)
{
if(node == NULL) return NULL;
if(node->key == key) return node;
if(key < node->key)
return floor(node->left, key);
Node<T1, T2>* t = floor(node->right, key);
if(t == NULL) return t;
else return node;
}
template<typename T1, typename T2>
T1 BST<T1, T2>::select(int k)
{
return select(root, k)->key;
}
template<typename T1, typename T2>
Node<T1, T2>* BST<T1, T2>::select(Node<T1, T2>* node, int k)
{
if(node == NULL) return NULL;
int t = size(node->left);
if(t > k) return select(node->left, k);
else if(t < k) return select(node->right, k - t - 1);
else return node;
}
template<typename T1, typename T2>
int BST<T1, T2>::rank(T1 key)
{
return rank(key, root);
}
template<typename T1, typename T2>
int rank(T1 key, Node<T1, T2>* node)
{
if(node == NULL) return 0;
if(key < node->key) return rank(key, node->left);
if(key > node->key) return 1 + size(node->left) + rank(key, node->right);
else return size(node->left);
}
void testBST()
{
BST<string, double>* bst = new BST<string, double>();
bst->add("a", 1.0);
bst->add("b", 2.0);
bst->add("c", 3.0);
bst->add("d", 30.0);
double _max = bst->max();
double _min = bst->min();
bst->deleMax();
_max = bst->max();
bst->deleMin();
_min = bst->min();
double r = bst->get("a");
r= bst->get("c");
}