二叉查找树（Binary Search Tree）,也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一颗空树或者具有下列性质的二叉树：
成都创新互联公司服务项目包括绥棱网站建设、
绥棱网站制作、绥棱网页制作以及绥棱网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，
绥棱网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到绥棱省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
（1）每个节点都有一个作为搜索依据的关键码（key），所有的节点的关键码互不相同。
（2）左子树上所有的关键码（key）都小于根节点点的关键码（key）。
（3）右子树上所有的关键码（key）都大于根节点的关键码（key）。
（4）左右子树都是二叉搜索树。
代码实现如下：
#include
using namespace std;
template
struct BSTreeNode{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
V _value;
BSTreeNode(const K& key,const V& value)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
{}
};
template
class BSTree{
typedef BSTreeNode Node;
public:
BSTree()
:_root(NULL)
{}
//非递归
bool Insert(const K& key, const V& value)
{
if (_root == NULL)
{
_root = new Node(key,value);
return true;
}
Node* parent = _root;
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;
}
}
if (parent->_key>key)
{
parent->_left = new Node(key,value);
}
else
{
parent->_right = new Node(key, value);
}
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
Node* Find(const K& key)
{
if (_root == NULL)
{
return NULL;
}
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return NULL;
}
bool Remove(const K& key)
{
if (_root == NULL)
{
return false;
}
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
break;
}
if (cur == NULL)
return false;
Node* del;
//删除节点的左为空
if (cur->_left == NULL)
{
del = cur;
if (parent == NULL)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete del;
}
//删除节点的右为空
else if (cur->_right == NULL)
{
del = cur;
if (parent == NULL)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete del;
}
//删除节点的左右都不为空
else
{ //找右树的最左节点，也就是右边最小的数
parent = cur;
Node* left = cur->_right;
while (left->_left)
{
parent = left;
left = left->_left;
}
del = left;
cur->_key = left->_key;
cur->_value = left->_value;
if (parent->_left == left)
{
parent->_left = left->_right;
}
else
{
parent->_right = left->_right;
}
delete del;
}
return true;
}
//递归
Node* FindR(const K& key)
{
return _FindR(_root,key);
}
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root,key,value);
}
bool RemoveR(const K& key)
{
return _RemoveR(_root,key);
}
protected:
void _InOrder(Node* root)
{
if (root != NULL)
{
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
}
Node* _FindR(Node* root,const K& key)
{
if (root == NULL)
{
return NULL;
}
if (root->_key == key)
{
return root;
}
if (root->_key > key)
{
return _FindR(root->_left,key);
}
else
{
return _FindR(root->_right,key);
}
return NULL;
}
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == NULL)
{
root = new Node(key,value);
return true;
}
if (root->_key > key)
{
return _InsertR(root->_left,key,value);
}
else
{
return _InsertR(root->_right,key,value);
}
return false;
}
bool _RemoveR(Node*& root, const K& key)
{
if (root == NULL)
{
return false;
}
if (root->_key > key)
{
return _RemoveR(root->_left,key);
}
else if (root->_key < key)
{
return _RemoveR(root->_right,key);
}
else
{
//删除的节点的左为空
if (root->_left == NULL)
{
root = root->_right;
}
//删除节点的右为空
else if (root->_right == NULL)
{
root = root->_left;
}
else
{ //找右边最左的节点（即右边最小的节点）替换删除的该节点（下面程序采用的）。
//或者找左边最右的节点（即左边大的节点）替换删除的该节点
Node* parent = root;
Node* left = root->_right;
while (left->_left)
{
parent = left;
left = left->_left;
}
root->_key = left->_key;
root->_value = left->_value;
if (parent->_left == left)
{
parent->_left = left->_right;
}
else
{
parent->_right = left->_right;
}
}
return true;
}
return false;
}
protected:
Node* _root;
};
#include "BSTree.h"
void Test1()
{
int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9};
BSTree bst;
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
bst.Insert(arr[i],i);
}
bst.InOrder();
BSTreeNode* ret1=bst.Find(8);
if (ret1)
{
cout << ret1->_key << ":" << ret1->_value << endl;
}
else
cout << "没有找到ret1" << endl;
BSTreeNode* ret2=bst.Find(22);
if (ret2)
{
cout << ret2->_key << ":" << ret2->_value << endl;
}
else
cout << "没有找到ret2" << endl;
bst.Remove(9);
bst.Remove(7);
bst.Remove(8);
bst.InOrder();
bst.Remove(0);
bst.Remove(1);
bst.Remove(2);
bst.Remove(3);
bst.Remove(4);
bst.Remove(5);
bst.Remove(6);
bst.Remove(7);
bst.Remove(8);
bst.Remove(9);
bst.InOrder();
}
void Test2()
{
int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9 };
BSTree bst;
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
bst.InsertR(arr[i], i);
}
bst.InOrder();
BSTreeNode* ret1 = bst.Find(7);
if (ret1)
{
cout << ret1->_key << ":" << ret1->_value << endl;
}
else
cout << "没有找到ret1" << endl;
BSTreeNode* ret2 = bst.Find(12);
if (ret2)
{
cout << ret2->_key << ":" << ret2->_value << endl;
}
else
cout << "没有找到ret2" << endl;
bst.RemoveR(8);
bst.RemoveR(7);
cout<运行结果：
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站题目：搜索二叉树-创新互联
标题链接：http://kswsj.cn/article/dcioej.html
