本篇内容介绍了“C++中如何实现搜索二叉树”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
成都创新互联2013年至今，是专业互联网技术服务公司，拥有项目成都网站建设、网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元阳城做网站,已为上家服务,为阳城各地企业和个人服务,联系电话:18982081108
二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
#pragma once
template
struct BSTreeNode
{
K _key;
V _value;
BSTreeNode* _left;
BSTreeNode* _right;
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 (NULL == _root)//若为空树
{
_root = new Node(key, value);
return true;
}
Node* parent = NULL;
Node* cur = _root;
//确定插入节点的位置
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else//已经存在key
{
return false;
}
}
//插入节点
if (key > parent->_key)
parent->_right = new Node(key, value);
else
parent->_left = new Node(key, value);
}
//Insert递归写法
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (NULL == root)
{
root = new Node(key, value);
return true;
}
if (key > root->_key)
return _InsertR(root->_right, key, value);
else if (key < root->_key)
return _InsertR(root->_left, key, value);
else
return false;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else
return cur;
}
return NULL;
}
//Find递归写法
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
Node* _FindR(Node* root, const K& key)
{
if (NULL == root)
return NULL;
if (key > root->_key)
return _FindR(root->_right, key);
else if (key < root->_key)
return _FindR(root->_left, key);
else
return root;
}
bool Remove(const K& key)
{
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
{
break;
}
}
if (NULL == cur)//没有该节点
{
return false;
}
Node* del;
if (NULL == cur->_left)//删除节点的左孩子为空
{
del = cur;
//删除的节点为根节点
if (NULL == parent)
{
_root = _root->_right;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
}
else if (NULL == cur->_right)//删除节点的右孩子为空
{
del = cur;
if (NULL == parent)
{
_root = _root->_left;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_left;
}
}
else//删除节点的左右孩子都不为空，找右子树最左节点代替该节点删除
{
parent = cur;
Node* leftmost = cur->_right;
while (leftmost->_left)
{
parent = leftmost;
leftmost = leftmost->_left;
}
del = leftmost;
cur->_key = leftmost->_key;
cur->_value = leftmost->_value;
if (leftmost == parent->_left)
parent->_left = leftmost->_right;
else
parent->_right = leftmost->_right;
}
return true;
}
//Remove递归写法
bool RemoveR(const K& key)
{
return _RemoveR(_root, key);
}
bool _RemoveR(Node*& root, const K& key)
{
if (NULL == root)
return false;
if (key > root->_key)
{
return _RemoveR(root->_right, key);
}
else if (key < root->_key)
{
return _RemoveR(root->_left, key);
}
else
{
Node* del = root;
if (NULL == root->_left)
{
root = root->_right;
}
else if (NULL == root->_right)
{
root = root->_left;
}
else
{
Node* leftmost = root->_right;
while (leftmost->_left)
{
leftmost = leftmost->_left;
}
swap(root->_key, leftmost->_key);
swap(root->_value, leftmost->_value);
return _RemoveR(root->_right, key);
}
delete del;
}
return true;
}
//中序遍历递归写法
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (NULL == root)
return;
_InOrder(root->_left);
cout<_key<<" ";
_InOrder(root->_right);
}
protected:
Node* _root;
};
void Test()
{
BSTree t;
int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i)
{
t.InsertR(a[i], i);
}
cout<_key<_key<_key<
“C++中如何实现搜索二叉树”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
文章名称：C++中如何实现搜索二叉树
本文路径：http://cxhlcq.com/article/gsghpc.html
重庆分公司
重庆分公司
