二叉搜索树
- 二叉搜索树概念
- 二叉搜索树的实现
- 结点类
- 主要接口
- 迭代插入
- 递归插入
- 中序遍历
- 迭代查找
- 递归查找
- 迭代删除
- 递归删除
- 拷贝构造
- 赋值
- 析构
- 搜索树的应用
- K模型
- KV模型
二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
例如：
二叉搜索树的实现
结点类
首先实现一个结点类，结点类中有3个成员变量：
template<class K>
struct BSTNode
{
BSTNode* _left;//左指针
BSTNode* _right;//右指针
K _key; //结点值
//构造函数
BSTNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
主要接口
template<class T>
class BSTree
{
typedef BSTNode<T> Node;
public:
BSTree()
:_root(nullptr)
{}
//插入
bool Insert(const K& key)；
//查找
Node* Find(const T& key);
//删除
bool Erase(const T& key);
//深拷贝
BSTree(const BSTree<K>& t);
//赋值
BSTree<K>& operator=(BSTree<K> t)
//析构
void Dostory(Node* root)
//中序遍历
void Inorder()
private:
Node* _root;//指向搜索树的根节点
};
迭代插入
当树为空的时候直接插入，树不为空时，例如：插入7，比5大就链接在5的右边，插入3，比5小，链接在5的左边。
动图演示：
具体实现：
//迭代插入
bool Insert(const K& key)
{
//树为空直接new一个结点
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//树不为空，大的插到右边，小的插到左边
Node* cur = _root;
Node* parent = cur;//记录一下parent
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,插入成功返回true,插入失败返回false,我们就可以知道插入成功与否，并且比允许插入一样的值。
递归插入
递归实现的思路基本差不多，递归插入的子函数接受参数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;
}
//比key大就递归右边
if (root->_key < key)
{
return _InsertR(root->_right,key);
}
//比key小就递归左边
else if(root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
用引用就不用找父亲结点了，此处体现了引用的价值。
中序遍历
搜索树的遍历建议使用中序遍历，我们来实现一下查看我们写的插入是否正确
//中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
//树为空直接返回
if (root == nullptr)
{
return;
}
//先递归左，打印值，再递归右
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
递归示意图：
此时插入的递归和非递归已完成。
迭代查找
查找就简单多了，比根节点大就到右边，小就到左边
Node* Find(const T& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return NULL;
}
递归查找
//递归查找
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
Node* _FindR(Node*& root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return root;
}
}
迭代删除
删除的思路;
删除左为空的分析
删除右为空的细节根删除左是一样的，要画图分析
在探讨一波删除左右都不为空的
动图演示;
具体代码实现：
bool Erase(const T& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//先开始找到要删除的结点
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//开始删除
//有1个孩子的
if (cur->_left == nullptr)
{
//没有左子树，让它的右做跟结点
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
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;
return true;
}
else
{
//有2个孩子的,替换法删除，找右子树中最小的
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left)
{
minParent = minRight;//记录minRight的父亲
minRight = minRight->_left;//往左边找
}
//保存key值
cur->_key = minRight->_key;
//判断待删结点是父亲的做还是右
if (minParent->_left == minRight)
{
minParent->_left = minRight->_right;
}
else
{
minParent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
递归删除
递归删除的思路：
具体代码实现：
//递归删除
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
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
{
//找到了开始删除
if (root->_left == nullptr)
{
//先保存待删结点
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)
{
//先保存待删结点
Node* del = root;
root = root->_left;
delete del;
}
else
{
Node* minRight = root->_right;
//先找到右子树的最小的结点
while (minRight->_left)
{
minRight = minRight->_left;
}
//先保存minRight的值
K min = minRight->_key;
//再次调用自己
_EraseR(root->_right,min);
//把root的值换位min的值
root->_key = min;
}
return true;
}
}
测试一下删除，测试的时候要测试把树删完
删除完成。
拷贝构造
先拷贝根节点的值，在拷贝左子树，然后右子树即可
//拷贝构造
BSTree(const BSTree<K>& t)
{
_root = _Copy(t._root);
}
Node* _Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copynode = new Node(root->_key);
//先拷贝左,在拷贝右
copynode->_left = _Copy(root->_left);
copynode->_right = _Copy(root->_right);
return copynode;
}
赋值
赋值跟之前的vector,list一样，用现代写法，传值然后交换即可
//赋值，调用拷贝构造,传值然后交换
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
析构
释放结点，按二叉树的后序来释放，最后将指向二叉树的指针置空即可。
//析构
~BSTree()
{
_Destory(_root);
_root = nullptr;
}
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
//先释放左，在释放右
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
搜索树的应用
K模型
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生
活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key，查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。
测试代码：
void test1()
{
kv::BSTree<string,string> dict;
dict.InsertR("basketball", "篮球");
dict.InsertR("sun", "太阳");
dict.InsertR("insert", "插入");
dict.InsertR("girl", "女孩");
string str;
while (cin>>str)
{
kv::BSTNode<string, string>* ret = dict.FindR(str);
if (ret == nullptr)
{
cout << "单词拼写错误，词库中没有这个单词" << str << endl;
}
else
{
cout << "中文翻译:" << ret->_value << endl;
}
}
}
效果如下：
只需录入单词就可以查到中文意思，这就是KV模型的应用。
KV模型完整代码
完整代码
搜索树变成单支效率就不行了，后序右AVL树和红黑树来解决问题。
