二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点。
因此，搜索二叉树中没有键值冗余的节点，通常可用来去重排序。
如图所示就是一棵二叉搜索树：
中序遍历结果为：0 1 2 3 4 5 6 7 8 9
需要注意的是：二叉搜索树在进行删除和插入操作后都需要再次进行调整，新得到的树也应该是二叉搜索树。
具体代码实现如下：
#include<iostream>
using namespace std;
template<class K>
class BinaraySearchNode
{
public:
BinaraySearchNode<K>* _left;
BinaraySearchNode<K>* _right;
BinaraySearchNode<K>* _parent;
K _key;
BinaraySearchNode(const K& key)
:_left(NULL),_right(NULL),_parent(NULL),_key(key)
{}
};
template<class K>
class BinarySearch
{
public:
typedef BinaraySearchNode<K> Node;
BinarySearch()
:_root(NULL)
{}
//插入
bool InSert(const K& key)
{
if (_root == NULL)
{
_root = new Node(key);
return true;
}
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
Node* tmp = new Node(key);
if (parent->_key > key)
parent->_left = tmp;
else if (parent->_key < key)
parent->_right = tmp;
return true;
}
//查找
Node* Find(const K& key)const
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
return cur;
}
return NULL;
}
//删除节点
bool Remove(const K& key)
{
if (_root == NULL)
return false;
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else//等于
{
if (cur->_left == NULL)
{
parent = cur->_parent;
if (parent == NULL)
{
_root = cur->_right;
delete cur;
cur = NULL;
return true;
}
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
cur = NULL;
}
if (cur->_right == NULL)
{
parent = cur->_parent;
if (parent == NULL)
{
_root = cur->_left;
delete cur;
cur = NULL;
return true;
}
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
cur = NULL;
}
if (cur->_left != NULL && cur->_right != NULL)
{
//替换法(注意根节点为空的情况）
Node* subRight = cur->_right;
Node* subParent = cur;
while (subRight->_left)
{
subParent = subRight;
subRight = subRight->_left;
}
cur->_key = subRight->_key;
if (subParent->_right == subRight)
subParent->_right = subRight->_right;
else
subParent->_left = subRight->_left;
delete subRight;
subRight = NULL;
}
return true;
}
}
return false;
}
//递归插入
bool _InSertR(Node*& root,const K& key)//递归插入
{
if (root == NULL)
return root = new Node(key);
if (root->_key < key)
return _InSertR(root->right,key);
if (root->_key > key)
return _InSertR(root->_left,key);
}
//递归删除
bool _RemoveR(Node*& root,const K& key)//注意：这里要加引用
{
if (root == NULL)
return false;
if (root->_left == NULL && root->_right == NULL)
{
if (root->_key == key)
{
delete root;
return true;
}
else
return false;
}
if (root->_key > key)
RemoveR(root->_left,key);
if (root->_key < key)
RemoveR(root->_right,key);
else
{
Node* cur = root;
if (cur->_left == NULL)
{
parent = cur->_parent;
if (parent == NULL)
{
root = root->_right;
delete cur;
cur = NULL;
}
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
cur = NULL;
}
if (cur->_right == NULL)
{
parent = cur->_parent;
if (parent == NULL)
{
_root = cur->_left;
delete cur;
cur = NULL;
return true;
}
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
cur = NULL;
}
if (cur->_left != NULL && cur->_right != NULL)
{
//替换法
Node* subRight = cur->_right;
Node* subParent = cur;
while (subRight->_left)
{
subParent = subRight;
subRight = subRight->_left;
}
cur->_key = subRight->_key;
if (subParent->_right == subRight)
subParent->_right = subRight->_right;
else
subParent->_left = subRight->_left;
delete subRight;
subRight = NULL;
}
return true;
}
}
//中序遍历
void InOrder()
{
_InOrder(_root);
}
protected:
void _InOrder(Node* root)
{
if (root == NULL)
return;
else
{
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
}
private:
Node* _root;
};
void Test()
{
BinarySearch<int> bs;
int a[] = { 5,3,1,4,7,6,8,9,2}; for (size_t i = 0; i < (sizeof(a) / sizeof(a[0])); ++i) { bs.InSert(a[i]); } bs.InOrder(); cout << endl; bs.Remove(5); bs.InOrder(); };
#define _CRT_SECURE_NO_WARNINGS 1
#include"binarysearch.h"
int main()
{
Test();
system("pause");
return 0;
}