专业模板建站提供商,能用二级域名做网站吗,做外贸什么网站,网页设计教程免费下载目录
一#xff0c;关于二叉搜索树
1.1 概念
1.2 基本结构
二#xff0c;二叉搜索树接口实现
2.1 插入
2.2 查找
2.3 打印
2.4* 删除
三#xff0c;二叉搜索树接口递归实现
3.1 查找
3.2 插入
3.3 删除 四#xff0c;二叉搜索树的默认成员函数
五#xff0c;…目录
一关于二叉搜索树
1.1 概念
1.2 基本结构
二二叉搜索树接口实现
2.1 插入
2.2 查找
2.3 打印
2.4* 删除
三二叉搜索树接口递归实现
3.1 查找
3.2 插入
3.3 删除 四二叉搜索树的默认成员函数
五测试代码
六二叉搜索树的应用
6.1 KeyValue
6.2 改造二叉搜索树
6.3 测试代码
6.3.1 查找单词
6.3.2 统计水果出现的次数 一关于二叉搜索树
1.1 概念
二叉搜索树又称二叉排序树具有以下性质 ①一节点左子树节点的值都小于该节点的值 ②一节点右子树的值都大于该节点的值 ③一节点的左右子树也是二叉搜索树 简单来说就是左孩子节点比我小右孩子节点比我大所以以中序遍历二叉搜索树时打印的结果是从小到大的所以二叉搜索树又被称为二叉排序树
1.2 基本结构
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public://接口以及默认成员函数实现private:Node* _root nullptr;
}
二二叉搜索树接口实现
2.1 插入
二叉搜索树的插入不难如果数为空直接新增根节点如果不为空比我小走左边比我大走右边走到空的时候新增节点并完成链接如下代码和注释
bool Insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}//先找到合适的插入位置Node* parent nullptr; //创建parent记录cur上一个节点位置方便后面链接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);//cur是局部变量出了函数作用域后没了不能直接cur赋值新节点//所以需要把前后链接起来这时候轮到我们的parent登场了if (key parent-_key) //插入的值比父节点大走右边{parent-_right cur;}else //插入的值比父节点小走左边{parent-_left cur;}return true;
}
2.2 查找
由于二叉搜索树的性质每次查找一个树的时候只需要走树的高度次就可以查到了查找效率非常高所以二叉搜索树还有个名称叫做二叉查找树
bool Find(const K key)
{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; //查找失败
}
2.3 打印
打印我们以中序遍历打印所以我们使用递归实现打印接口如下代码
public:void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}2.4* 删除
由于二叉搜索树关联式容器的特殊性质删除一个节点会改变整个容器的结构与性质所以每个关联式容器的删除操作需要做非常多的处理
对于二叉搜索树的删除我们大致分为下面几个情况 ①删除一个节点需要让被删除节点的父节点指向被删除节点的左孩子节点 ②删除一个节点需要让被删除节点的父节点指向被删除节点的右孩子节点 ③在被删除节点的右子树找一个最大值的节点替换两个节点的值再进行删除或者找左子树最大的点替换 如下图 具体实现结合下面代码和注释
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、左为空if (cur-_left nullptr)//要删除的节点的左子树为空{if (cur _root)//极端情况要干掉的是根{_root cur-_right;}else{if (cur parent-_left) //cur是父亲的左{parent-_left cur-_right;//让父亲的左指向要删除节点的右因为cur的左为空}else //cur是父亲的右{parent-_right cur-_right; //让父亲的右指向要删除节点的右因为cur的左为空}}delete cur;cur nullptr;}// 2、右为空else if (cur-_right nullptr)//要删除的节点的右子树为空{if (_root cur)//极端情况要干掉的是根{_root cur-_left;}else{if (cur parent-_left) //cur是父亲的左{parent-_left cur-_left; //让父亲的左指向要删除节点的左因为cur的右为空}else //cur是父亲的右{parent-_right cur-_left;//让父亲的右指向要删除节点的左因为cur的右为空}}delete cur;cur nullptr;}// 3、左右都不为空else{// 找右子树最小节点 或 找左子树的最大节点 替代要删除的值Node* pminRight cur;Node* minRight cur-_right;//找右树最小节点while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;//交换要删除的值if (pminRight-_left minRight){pminRight-_left minRight-_right;}else //这里看不懂可以结合上面的那个图中的要删除3和8的场景来理解{pminRight-_right minRight-_right;}delete minRight;}return true;}}//没找到要删除的值不存在return false;
}
三二叉搜索树接口递归实现
3.1 查找
public:bool FindR(const K key)///递归查找{return _FindR(_root, key);}private:bool _FindR(Node* root,const K key)//递归查找子函数{//最多找高度次O(h) h是树的高度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;}
3.2 插入
实现插入子递归函数的时候我们选择用Node* root做函数参数原因如下
插入的目标是插入合适的值并且和父亲链接起来比如要在某个节点右边插入一个值递归时就是 _Insert(root-right,key)我们用Node* root之后这个root就间接代表了上一个节点的right指针然后我们再root new Node(key)相当于生成一个新节点并直接赋值给父节点的右间接完成链接如下代码
public:bool InsertR(const K key)//递归插入{return _InsertR(_root, key);}private:bool _InsertR(Node* root, const K key)//递归插入{if (root nullptr){root new Node(key);//root是形参所以前面用引用return true;}if (root-_key key)return _InsertR(root-_right, key);else if (root-_key key)return _InsertR(root-_left, key);else //相等return false;}
3.3 删除
删除我们和插入同理用Node* root做返回值利用我们上面的思想完成递归实现如下代码
public:bool EraseR(const K key){return _EraseR(_root, key);}private:bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (key root-_key)return _EraseR(root-_right, key);else if (key root-_key)return _EraseR(root-_left, key);else//找到了开始删除{Node* del root;if (root-_left nullptr){//间接完成链接这里的root在递归中可以间接认为是上一个节点的right或left只是用了一个root引用来代替root root-_right; }else if(root-_right nullptr){root root-_left;}else{//找右子树最小最左节点替换删除Node* min root-_right;while (min-_left){min min-_left;}swap(root-_key,min-_key);return _EraseR(root-_right, key);}delete del;return true;}}四二叉搜索树的默认成员函数
public://由于我们自己实现了析构函数所以编译器不会自动生成默认构造//这条语句强制编译器生成默认构造函数BSTree() default;BSTree(const BSTreeK t)//拷贝构造{_root _Copy(t._root);}~BSTree()//析构{_Destory(_root);}//t2t1BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}private:Node* _Copy(Node* root){if (root nullptr){return nullptr;}Node* copyRoot new Node(root-_key);copyRoot-_left _Copy(root-_left);copyRoot-_right _Copy(root-_right);return copyRoot;}void _Destory(Node* root){if (root nullptr){return;}//先删左再删右再删根后序_Destory(root-_left);_Destory(root-_right);delete root;root nullptr;}
五测试代码
int main()
{BSTreeint t1;int a[] { 8,3,1,10,6,4,7,14,13,4,3,4 };for (auto e : a){t1.Insert(e);}BSTreeint t2 t1;t1.InOrder();t2.InOrder();cout ---------------- endl;t1.Insert(15);t1.Insert(5);t2.Erase(8);t2.Erase(13);cout t1.Find(15) endl;cout t2.Find(13) endl;cout ---------------- endl;t1.InOrder();t2.InOrder();return 0;
}
六二叉搜索树的应用
6.1 KeyValue
1Key模型只有Key作为关键码结构中只需存储Key搜索时只搜索Key
比如给一个单词word判断该单词是否拼写正确方法如下 ①以词库中所有单词集合中的每个单词作为Key构建一颗搜索二叉树 ②在二叉搜索树中查找该单词的存在存在则拼写正确不存在则拼写错误 2KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。
①比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word,chinese就构成一种键值对
②再比如统计单词次数统计成功后给定单词就可以快速找到其出现的次数单词与其出现次数就是word,count就构成一种键值对
6.2 改造二叉搜索树
templateclass K, class V
struct BSTreeNode
{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}
};
templateclass K, class V
class BSTree
{typedef BSTreeNodeK, 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);//cur是局部变量出了函数作用域后没了需要把前后链接起来//创建parent记录cur上一个节点位置方便链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}void InOrder(){_InOrder(_root);}Node* Find(const K 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 nullptr;}
private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key : root-_value endl;;_InOrder(root-_right);}bool FindR(const K key)///递归查找{return _FindR(_root, key);}Node* _root nullptr;
};
6.3 测试代码
6.3.1 查找单词
void TestBSTree1()
{BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(left, 左边);dict.Insert(right, 右边);dict.Insert(string, 字符串);dict.Insert(insert, 插入);string str;while (cin str){BSTreeNodestring, string* ret dict.Find(str);if (ret){cout : ret-_value endl;}else{cout -无此单词 endl;}}
} 6.3.2 统计水果出现的次数
void TestBSTree2()
{string arr[] { 苹果,苹果, 苹果, 苹果, 苹果, 香蕉,草莓,苹果, };BSTreestring, int countTree;for (auto str : arr){//BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret)//找到水果名{ret-_value;}else//没有找到水果该水果第一次出现{countTree.Insert(str, 1);}}countTree.InOrder();
}
