(一) 什么是二叉查找树
二叉查找树，也叫二叉搜索树，英文是Binary Search Tree，简称BST，它是以一颗二叉树来组织的，如图一所示，这样一颗树可以使用链表数据结构来表示，其中每个结点就是一个对象。除了key和数据之外，每个结点还包含属性left、right 和 p，它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为NIL。
图一 二叉搜索树
(二) 二叉查找树实现
1. 结点的定义
结点应该包括key 、 value 、left 和 right 四个元素。
template<class K, class V>
struct BST_node
{
K _key;
V _value；
BST_node<K, V> *_left;
BST_node<K, V> *_right;
BST_node(const K& key, const V& value)
:_key(key), _value(value), _left(NULL), _right(NULL)
{}
};
2. BST对象的定义
template<class K, class V>
class BST_tree
{
public:
BST()
:_root(NULL)
{}
bool Insert(const K& key, const V& value); //插入新结点
bool Remove(const K& key); //删除结点
BST_node<K, V>* Find(const K& key); //查找关键字
void In_Order_Print_Tree(); //中序遍历打印
void Post_Order_Print_Tree(); //后序遍历打印
void Pre_Order_Print_Tree(); //前序遍历打印
protected:
BST_node<K, V>* _root;
};
3. BST的插入操作
图二 BST的插入操作
template<class K, class V>
bool Insert(const K& key, const V& value)
{
if( _root == NULL )
{
_root = new BST_node<K, V>(key, value);
return true;
}
BST_node<K, V>* cur = _root;
BST_node<K, V>* parent = _root;
while( cur ) /*寻找插入位置的父结点parent*/
{
if( cur -> _key > key )
{
parent = cur;
cur = cur -> _left;
}
else if( cur -> _key < key )
{
parent = cur;
cur = cur -> _right;
}
else
{
return false;
}
}
if( key < parent -> _key ) /*小于父结点，插入到左结点*/
parent -> _left = new BST_node<K, V>(key, value);
else /*大于父结点，插入到左结点*/
parent -> _right = new BST_node<K, V>(key, value);
return ture;
}
4. BST的查询操作
BST_node<K, V>* Find(const K& key)
{
if( _root == NULL )
return NULL;
BST_node<K, V>* cur = _root;
while( cur )
{
if( key == cur -> _key )
return cur;
else if( key > cur -> _key ) /*待查询key大于当前节点的key，则从其右子树再寻找*/
cur = cur -> _right;
else /*待查询key小于当前节点的key，则从其左子树再寻找*/
cur = cur -> _left;
}
return NULL; /*查询不到该key*/
}
5. BST的删除操作
从一颗二叉搜索树 T 中删除一个结点 y 的整个策略分三种情况，如图三。
- 如果 y 没有孩子结点，那么只是简单的将它删除，并修改 y 的父亲结点，用NULL来替换 y 结点。
- 如果 y 只有一个孩子， 那么删除 y 结点后，需要将其孩子提升到 y 的位置，并修改 y 的父结点， 用 y 的孩子来替换 y。
- 如果 y 有两个孩子，需要从 y 结点的右子树中寻找出一个最小key的结点 x， 让 x 占据原来 y 所在的位置， 并且y 的原来右子树成为 x 的新的右子树，y 的左子树成为 x 的新的左子树 。同时需要修改 x结点的父结点和 y结点父结点。
如图三所示。
图三
bool Remove(const K& key)
{
// 1.空树，根节点为空
// 2.key结点没有有子树
// 3.key结点有子树
// a.key结点只有一个子树，左子树或者右子树
// b.key结点有左右子树
if( _root == NULL )
return false;
if( _root -> _left == NULL && _root -> _right == NULL )
{ /*只有根结点*/
if( key == _root -> _key )
{
delete _root;
_root = NULL;
return true;
}
else
return false;
}
BST_node<K, V>* cur = _root;
BST_node<K, V>* parent= _root;
BST_node<K, V>* del= NULL;
while( cur )
{
if( cur -> _key > key )
{
parent = cur;
cur = cur -> _left;
}
else if( cur -> _key < key )
{
parent = cur;
cur = cur -> _right;
}
else
{
/*找到该删除的结点*/
del = cur;
if( cur -> _left == NULL )
{ /*无左子树*/
if( cur -> _right != NULL )
{ /*但有右子树*/
if( parent -> _left == cur)
parent -> _left = cur -> _right;
else
parent -> _right = cur -> _right;
}
else
{ /*也无右子树*/
if( parent -> _left == cur)
parent -> _left = NULL;
else
parent -> _right = NULL;
}
}
else if( cur -> _right == NULL )
{ /*有左子树，但无右子树*/
if( parent->left == cur )
parent -> _left = cur -> _left;
else
parent -> _right = cur -> _right;
}
else
{ /*既有左子树和右子树*/
BST_node<K, V>* first_left = cur -> _right ; /*寻找右子树的最小的结点*/
while( first_left )
{
parent = first_left;
first_left = first_left -> _left;
}
del = first_left;
swap( cur -> _key, first_left -> _key );
swap( cur -> _value, first_left -> _value );
if( parent -> _left == first_left ) /*待删除结点的右子树的左子树非空*/
parent -> _left = first_left -> _right;
else if( cur -> _left = first_left ) /*待删除结点的右子树的左子树为空*/
cur -> _right = first_left -> _right;
}
delete del;
return true;
}
return false;
}
(三) 测试代码
void test()
{
}
