文章目录
二叉搜索树
-
特点：左子树都小于等于根，右子树都大于等于根
-
完全二叉树：h = logN
-
单分支的二叉树：h = N
-
二插搜索树有两个版本，一个冗余的，一个不冗余的
不冗余：和树里面值相等的不允许插入
冗余：和树里面值相等的保证都插入到同一边
实现
实现的是不冗余版本
树的节点
// Binary Search Tree
// 节点的结构
template<class K>
class BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
// 构造
BSTNode(const T& key)
:_key(key),
left(nullptr),
right(nullptr)
{}
};
树的结构
// 树
template<class K>
class BSTree
{
// typedef BSTNode<K> Node;
using Node = BSTNode<K>;
public:
// 实现的函数
private:
Node* root = nullptr;
};
插入
可以用递归也可以用循环
建议用循环
设计两个指针，为了让cur(要插入节点的指针)和parent(上一个节点的指针)链接起来，只定义一个cur链接不起来
// 插入
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
// 插入成功返回true
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 冗余版本
// 和key相等都插入到右边
if (cur->_key <= key)
{
parent = cur;
cur = cur->_right;
}
else
{
parent = cur;
cur = cur->_left;
}
// 不冗余版本
//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;
}*/
if (parent->_key <= key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
中序遍历
N 1 N 3 N 4 N 6 N 7 N 8 N 10 N 13 N 14 N
1 3 4 6 7 8 10 13 14
中序遍历之后搜索二叉树就是升序的了
// 给类外使用,因为类外不知道_root根
void Inorder()
{
_Inorder(_root);
}
private:
// 中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
private:
Node* _root = nullptr;// 生成默认构造,给缺省值nullptr
};
查找
- 从根开始比较，x比根大往右边找，比x根小往左边找
- 最多查找高度次，走到空，还没找到，这个值就不存在
- 如果不支持插入相等的值，找到x就返回
- 如果支持插入相等的值，就有多个x存在，一般返回中序找到的第一个x,比如下图中，查找3，返回1的右孩子的那个3
- 如果不考虑平衡的话，全都插入到右边，左根右，找到的第一就可以返回，考虑平衡的话，就要进行旋转，左根右，就一直往它的左边找直到找到空之前的第一个3（就一直找直到左树找不到3，返回找不到之前的一个，就是第一个插入的3），平衡二叉树下回会具体说
1 3 3
查找就更简单了,可以用循环直接写
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key == key)
{
return true;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
}
return false;
}
删除
- 没有孩子的节点删除：删除叶子是最好删的，把叶子delete,再把parent的那个指针指向空
- 有一个孩子的节点删除：parent节点指向N节点的孩子，再把N节点释放，左为空，或右为空
- 有两个孩子的节点删除：用替换法删除，找要删除的该节点的左子树的最大值的节点R（最右节点）或者找右子树的最小值的节点R（最左节点）代替N，因为用这两个的任意一个都满足二叉搜索树的规则。
- 代替是指：N和R两个节点的值交换，转而变成删除R节点
前两种情况：
最后一种情况：
- reparent->left = replace
reparent->left = replace->right - reparent->right = replace
reparent->right = repalce->right
3.
// 删除
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
{
// 左为空
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
{
// 删除
// reparent = cur,如果不进入循环cur,
// 如果为reparent为空就对空指针解引用了
// 进循环才会更新
Node* reparent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
reparent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
// 删除repalce
if (reparent->_left == replace)
reparent->_left = replace->_right;
else
reparent->_right = replace->_right;
delete replace;
}
return true;
}
}
// _root == nullptr
return false;
}
key的搜索场景
- 搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
- 检查篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示
key/value搜索场景
- 一个key对应一个value
- 每一个关键码key，都有与之对应的值value，value可以是任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value
- 简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文
- 统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数
- set key
- map key/value
有上面两个容器就不需要自己实现底层的搜索树了
#pragma once
#include<iostream>
using namespace std;
namespace key_value
{
// Binary Search Tree
// 节点的结构
template<class K,class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K,V>* _left;
BSTNode<K,V>* _right;
// 构造
BSTNode(const K& key,const V& value)
:_key(key),
_value(value),
_left(nullptr),
_right(nullptr)
{}
};
// 树
template<class K,class V>
class BSTree
{
// typedef BSTNode<K,V> Node;
using Node = BSTNode<K,V>;
public:
// 插入
bool Insert(const K& key,const V& value)
{
if (_root == nullptr)
{
_root = new Node(key,value);
// 插入成功返回true
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 冗余版本
// 和key相等都插入到右边
if (cur->_key <= key)
{
parent = cur;
cur = cur->_right;
}
else
{
parent = cur;
cur = cur->_left;
}
// 不冗余版本
//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;
}*/
if (parent->_key <= key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
// 删除
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
{
// 左为空
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
{
// 删除
// reparent = cur,如果不进入循环cur,
// 如果为reparent为空就对空指针解引用了
// 进循环才会更新
Node* reparent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
reparent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
// 删除repalce
if (reparent->_left == replace)
reparent->_left = replace->_right;
else
reparent->_right = replace->_right;
delete replace;
}
return true;
}
}
// _root == nullptr
return false;
}
// 查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key == key)
{
return cur;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
}
return nullptr;
}
// 给类外使用,因为类外不知道_root根
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
// 中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << ":" << root->_value << " ";
_Inorder(root->_right);
}
private:
Node* _root = nullptr;// 生成默认构造,给缺省值nullptr
};
}
namespace key
{
// Binary Search Tree
// 节点的结构
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
// 构造
BSTNode(const K& key)
:_key(key),
_left(nullptr),
_right(nullptr)
{
}
};
// 树
template<class K>
class BSTree
{
// typedef BSTNode<K> Node;
using Node = BSTNode<K>;
public:
// 插入
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
// 插入成功返回true
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 冗余版本
// 和key相等都插入到右边
if (cur->_key <= key)
{
parent = cur;
cur = cur->_right;
}
else
{
parent = cur;
cur = cur->_left;
}
// 不冗余版本
//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;
}*/
if (parent->_key <= key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
// 删除
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
{
// 左为空
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
{
// 删除
// reparent = cur,如果不进入循环cur,
// 如果为reparent为空就对空指针解引用了
// 进循环才会更新
Node* reparent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
reparent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
// 删除repalce
if (reparent->_left == replace)
reparent->_left = replace->_right;
else
reparent->_right = replace->_right;
delete replace;
}
return true;
}
}
// _root == nullptr
return false;
}
// 查找
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key == key)
{
return true;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
}
return false;
}
// 给类外使用,因为类外不知道_root根
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
// 中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
private:
Node* _root = nullptr;// 生成默认构造,给缺省值nullptr
};
}
key的场景
int main()
{
key_value::BSTree<string, string> dict;
//BSTree<string, string> copy = dict;
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插入");
dict.Insert("string", "字符串");
string str;
// cin >> str ctrl+z换行结束
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << "->" << ret->_value << endl;
}
else
{
cout << "无此单词，请重新输入" << endl;
}
}
return 0;
}
key/value的场景
int main()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果","香蕉" };
key_value::BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找水果在不在搜索树中
// 1、不在，说明水果第一次出现，则插入<水果, 1>
// 2、在，则查找到的结点中水果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == nullptr)
{
countTree.Insert(str, 1);
}
else
{
// 统计水果出现的次数,修改value
ret->_value++;
}
}
countTree.Inorder();
return 0;
}
搜索树存在的拷贝和析构的问题
- 底层都要走深拷贝
// 写了拷贝构造不会生成默认构造了
// 强制生成构造
// BSTree() 构造函数的声明
BSTree() = default;
// 拷贝
BSTree(const BSTree& t)
{
_root = Copy(t._root);
}
// 赋值
// 现代写法
BSTree& operator=(BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}
// 析构
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
private:
void Destroy(Node* root)
{
if (root == nullptr)
return;
// 左右根,倒着往上析构,后序
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
// 中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << ":" << root->_value << " ";
_Inorder(root->_right);
}
// 拷贝
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
// 构建根
Node* newroot = new Node(root->_key, root->_value);
// 构建左树
newroot->_left = Copy(root->_left);
// 构建右树
newroot->_right = Copy(root->_right);
return newroot;
}