目录
二叉搜索树又称二叉排序树,它或者是一棵空树 , 或者是具有以下性质的二叉树:
如下如所示:
代码实现:(部分代码复制过来可能存在缩进问题)
bool Find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
递归方式实现:
因为实现递归方式需要每次都传一次根节点,所以我们需要封装一个私有函数 _FindR 实现。
思路:
如果是root为空,则返回false。如果非空,先比较查找数key与当前root中的_key的大小,大则从右边开始查找,小则从左边开始查找,层层递归,最后直到找到或者为空返回。
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
代码实现:
bool Insert(const K& key)
{
//空树情况
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//不能重复插入
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
递归方式实现:
思路:
当我们root为空的时候,直接让root指向新建的节点。非空的时候就一直递归向下。递归的思路还是非常简单的。
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情 况:
思路:先找到删除的数据的位置,
删除节点的左节点为空的时候:
a)如果该节点是_root,直接将_root指向删除数据的右节点。
b)不是_root时,还需要删除节点的父节点来接受删除节点的右节点。
右节点为空的时候同理,只是左右位置改变一下。
当左右节点都不为空的时候:
从 cur 的右节点开始一直向左找到最小节点 minRight ,这时候 minRight 还可能有右节点(因为minRight最小所以一定没有了左节点),我们先把 cur 的指向的值改成 minRight 指向的值,然后让 minRight 的父节点 parent 指向自己的右节点。
代码:
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//1.左边空
//2.右边空
//3.两边都不为空,替换删除
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* parent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
parent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight == parent->_left)
{
parent->_left = minRight->_right;
}
else
{
parent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
递归实现:
思路:
用值来判断,如果根节点的值小于 key ,那就右节点作为跟继续递归,反之则左节点作为根递归。
如果根节点等于key的时候:a) 如果有一边为空,那么根节点向另一边移动一个,然后删除原根节点。 b)如果两边都不为空,在从根节点的右节点开始向左寻找最小节点 minRight ,然后将root中的值与 minRight 中的值交换,然后根节点的右节点作为根节点继续递归。这样就转化成了在子树中删除对应节点。
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
swap(root->_key, minRight->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
因为每次需要传根节点,所以我们写一个函数copy来实现拷贝功能。
copy函数原理:左右节点向上逐级链接形成一棵越来越大的树。
重载运算符=号:只需要与形参交换根节点,子节点自然也就跟着根节点过来了。
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
因为销毁需要递归销毁,要传参根节点,我们也需要写一个destroy函数来实现。
先递归删除左右节点,然后删除根节点。
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
}
namespace K
{
//搜索二叉树节点
template<class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
bool Insert(const K& key)
{
//空树情况
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//不能重复插入
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
bool Find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//1.左边空
//2.右边空
//3.两边都不为空,替换删除
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
Node* parent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
parent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight == parent->_left)
{
parent->_left = minRight->_right;
}
else
{
parent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
swap(root->_key, minRight->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
private:
Node* _root = nullptr;
};
}
K就是二叉搜索树的第一个参数key,V就是第二个参数value。通过加入第二个参数,我们可以用二叉搜索树实现很多的功能。例如:翻译单词,输出数字中不同的词语出现的次数。
实现翻译功能
代码:
namespace KV
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
,_value(value)
, _right(nullptr)
, _key(key)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
//空树情况
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//不能重复插入
return false;
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
if (_root == nullptr)
{
return nullptr;
}
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " " << root->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}
void test2()
{
KV::BSTree<string, string> dict;
+ dict.Insert("sort", "排序");
dict.Insert("apple", "苹果");
dict.Insert("excellent", "非常好的");
dict.Insert("outgoing", "外向的");
dict.Insert("welcome","欢迎");
string str;
while (cin >> str)
{
KV::BSTreeNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "查无此单词" << endl;
}
}
}
在我们实现翻译单词功能的时候,我们key对应的是英文单词,value对应的就是中文意思。
void test3()
{
string arr[] = { "苹果", "西瓜", "香蕉", "草莓","苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
KV::BSTree<string, int> count_tree;
for (auto numb : arr)
{
KV::BSTreeNode<string, int>* ret = count_tree.Find(numb);
if (ret == nullptr)
{
count_tree.Insert(numb, 1);
}
else
{
ret->_value++;
}
}
count_tree.InOrder();
}
当我们实现统计次数的功能的时候,这时候的value对应的就是次数,当某个名词已经有了,那么再次插入的时候我们只需要将次数++即可。