旅游网站名称设计,百度模板网站模板,百度关键词挖掘查询工具,网站子域名查询目录
一、二叉搜索树的定义 二、二叉搜索树的实现#xff1a;
1、树节点的创建--BSTreeNode 2、二叉搜索树的基本框架--BSTree
3、插入节点--Insert 4、中序遍历--InOrder
5、 查找--Find
6、 删除--erase
完整代码#xff1a;
三、二叉搜索树的应用
1、key的模型
1、树节点的创建--BSTreeNode 2、二叉搜索树的基本框架--BSTree
3、插入节点--Insert 4、中序遍历--InOrder
5、 查找--Find
6、 删除--erase
完整代码
三、二叉搜索树的应用
1、key的模型 判断在不在
2、key/value的模型通过key找value
key/value的应用场景
应用场景1--中英文互译
应用场景2--统计水果出现次数 四、二叉搜索树性能分析 一、二叉搜索树的定义 二叉搜索树也称为搜索二叉树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二、二叉搜索树的实现
这里最好不用递归递归比非递归更复杂故用非递归实现
分两个文件 BSTree.hpp(因为要用模板实现而模板的实现和声明要放在一起的若用模板实现就可用.hpp为后缀和 Test.c 1、树节点的创建--BSTreeNode 树是由节点组成的故应写个BSTreeNode用来表示每个树节点_left表示左指针_right表示右指针还有一个位置用来存值_key因为无法确定存的是什么类型的值故用模板来实现通用设置成struct是因为树的节点对外是公开的外部都可以访问的 templateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;
};2、二叉搜索树的基本框架--BSTree 对于树的成员变量一个根节点即可 templateclass K
class BSTree //Binary Search Tree
{typedef BSTreeNodeK Node;
public:private:Node* _root nullptr;可以直接定义,就一个成员变量无需写个构造函数
}; 3、插入节点--Insert 这个函数需要有返回值的以bool作为返回类型因为这棵树中不允许数据冗余即不能出现相同的数据。 插入就是用性质左子树的值都比当前根节点的值小右子树的值都比当前根节点的值大 若插入一个数据key从根节点用cur指针来表示当前位置开始往下比就好了 ①、如果key比当前节点的值大那就接着往右走 ②、如果key比当前节点的值小那就接着往左走 对于①②直到找到一个空位置插入即可 ③、如果走的过程中遇到相等的值说明该key值不能插入但要注意一个条件如果这棵树本来就为空那就直接把数据插入到根节点中就好 链接问题 插入一个节点必然要与树链接若不链接这个节点就是个临时数据出了作用域就没了但若把他链接到树上就能正常访问了故这里采用双指针法cur表示当前节点再定义一个parent每次cur走之前先把cur赋值给parent这样最后cur走到空了parent能记录到cur的上一位置而这上一位置就是要找的cur要与其链接的位置至于cur插入到parent的左还是右若值比parent的值大则插到右边小则插到左边 bool Insert(const K key)
{if (_root nullptr){//若为空树就给它一个节点_root new Node(key);//new是开空间初始化所以要调用构造函数你要写的return true;}Node* cur _root;//从根节点开始比较Node* parent nullptr;while (cur){//都会找一个空位置插入不会说挪动节点来进行插入if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//若在走的过程中遇到相同的数据返回假这个数据无法插入return false;}}cur new Node(key);//向这个空位置插入数据//利用parent的位置与cur连接if (parent-_key key)parent-_left cur;//比根节点小链接到左边elseparent-_right cur;//比根节点大链接到右边return true;
} 4、中序遍历--InOrder 这里用两个成员函数实现为什么中序遍历你要传树的根节点而根节点就是类的私有成员变量而你的中序遍历一定是在类外使用的无法直接访问_root 解决方法 法一、写个成员函数获得一下_root是可以的 法二、用两个成员函数即用InOrder来传这个_root成员函数访问你_root一定是没问题的那么_InOrder直接用来中序遍历即可调用时直接调用InOrder即可 void InOrder()
{_InOrder(_root);cout endl;
}
//下面的可以放到private里面
void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
} 下面利用写的插入和中序遍历测试下代码
void testTree()
{BSTreeint t;int a[] { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){//数组是可以用迭代器来遍历的t.Insert(e);//插入节点到树中}t.InOrder();//中序遍历
} 5、 查找--Find bool Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key) {cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;//说明相等则找到了返回真}}return false;//走到空还没找到说明没有此数据
} 6、 删除--erase 1、观察现象 删除2让父亲指向我的右删除8让父亲指向我的右5不好删因为他有两个孩子 左为空父亲指向我的右右为空父亲指向我的左叶子节点可以归纳为左为空右为空也行这里就假设用左为空因为叶子的左右都为空它父亲的指向他的左还是右均可 左为空 2、细节考虑 A、待删除节点左为空或右为空的情况叶子结点可归类为左为空 删除一个节点是让其父亲Parent的左指针还是右指针指向cur 【若cur的左子树为空】看cur到底是父亲的左子树还是右子树若是父亲的左子树则让父亲的左指向cur右子树 若为右子树则让父亲的右指向cur的右子树 【若cur的右子树为空】若是父亲的左子树则让父亲的左指向cur左子树 若为右子树则让父亲的右指向cur的左子树 B、待删除节点左右都不为空的情况 节点的左右子树都不为空不能直接删除直接删除会导致二叉搜索树混乱故用替代法删除。 因为要符合左子树都比根节点小右子树都比根节点大的性质故要找左子树的最大节点或右子树的最小节点去替代它。左子树最右边的节点是左子树最大节点右子树的最左边的节点是右子树最小节点【故假设我们下面就用右子树的最小节点】 比如删除7可以用87的右子树的最左节点来替代那么替换完后我删除这个7就可以直接删了那么这个问题又转换到了被删除节点的左为空或者右为空因为替换节点一定要么是最左边的节点要么是最右边的节点不一定是叶子结点那这个替换节点的左右子树一定存在左子树右子树有个为空的情况 所以删除 分三种情况 问题1 删除一定要找到父亲因为删完了还存在链接关系所以单单用find去找是不行的他找不到他的父亲节点故还是用双指针法 因为链接问题所以删除关键看cur是在父亲的左还是右而不是看cur的左边为空还是右边为空这不符合所有场景 问题2 最左节点不一定就是叶子结点比如这里删除7它的右子树的最左节点是8则8替换完7后8要被删除他被删除完后parent的右指针要指向rightMin的右节点 问题3 parent初始值不能为nullptr若删除7【che指针指向7】因为要删除curRightmin刚上来就8Rightmin的左子树为空while循环都没进去而parent它还是nullptr那后续的链接肯定会有问题的所以parent应该一上来就赋值为cur而不是nullptr 问题4 若要删除的节点是根节点也要特别考虑左为空则让根它的右节点右为空则让根它的左节点 bool Erase(const K key)
{Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//找到了开始删除//1.左为空if (cur-_left nullptr){if (cur _root)_root cur-_right;else{if (parent-_left cur)parent-_left cur-_right;//cur在父亲的左边就让父亲的左指向cur的左elseparent-_right cur-_right;//cur在父亲的右边就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root)_root cur-_left;else{if (parent-_right cur)parent-_right cur-_left;//cur在父亲的右边就让父亲的右指向cur的左elseparent-_left cur-_left;//cur在父亲的左边就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent cur;Node* Rightmin cur-_right;//若用右树的最小节点即右树最左节点while (Rightmin-_left){//最左节点的左子树一定为空故为判断条件parent Rightmin;//替换节点不一定是叶子结点故还要用parent来链接Rightmin Rightmin-_left;}cur-_key Rightmin-_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树则父亲的右指向它的右//若它是parent的左子树则父亲的左指向它的左if (Rightmin parent-_left)parent-_left Rightmin-_right;elseparent-_right Rightmin-_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到则该数据不存在
}
完整代码
BSTree.hpp
#pragma once
#includeiostream
using namespace std;templateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;};
templateclass K
class BSTree //Binary Search Tree
{typedef BSTreeNodeK Node;
public:bool Insert(const K key){if (_root nullptr){//若为空树就给它一个节点_root new Node(key);//new是开空间初始化所以要调用构造函数你要写的return true;}Node* cur _root;//从根节点开始比较Node* parent nullptr;while (cur){//都会找一个空位置插入不会说挪动节点来进行插入if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//若在走的过程中遇到相同的数据返回假这个数据无法插入return false;}}cur new Node(key);//向这个空位置插入数据//利用parent的位置与cur连接if (parent-_key key)parent-_left cur;//比根节点小链接到左边elseparent-_right cur;//比根节点大链接到右边return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key) {cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;//说明相等则找到了返回真}}return false;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//找到了开始删除//1.左为空if (cur-_left nullptr){if (cur _root)_root cur-_right;else{if (parent-_left cur)parent-_left cur-_right;//cur在父亲的左边就让父亲的左指向cur的左elseparent-_right cur-_right;//cur在父亲的右边就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root)_root cur-_left;else{if (parent-_right cur)parent-_right cur-_left;//cur在父亲的右边就让父亲的右指向cur的左elseparent-_left cur-_left;//cur在父亲的左边就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent cur;Node* Rightmin cur-_right;//若用右树的最小节点即右树最左节点while (Rightmin-_left){//最左节点的左子树一定为空故为判断条件parent Rightmin;//替换节点不一定是叶子结点故还要用parent来链接Rightmin Rightmin-_left;}cur-_key Rightmin-_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树则父亲的右指向它的右//若它是parent的左子树则父亲的左指向它的左if (Rightmin parent-_left)parent-_left Rightmin-_right;elseparent-_right Rightmin-_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到则该数据不存在}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;//可以直接定义,就一个成员变量无需写个构造函数
};void testTree()
{BSTreeint t;int a[] { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){//数组是可以用迭代器来遍历的t.Insert(e);//插入节点到树中}t.InOrder();//中序遍历
} Test.cpp
#includeBSTree.hppint main()
{testTree();return 0;
}
三、二叉搜索树的应用
搜索树使用场景
1、key的模型 判断在不在 比如进入校园要刷校园卡卡本质里面有芯片芯片上存储信息把学校所有学员的信息存到二叉搜索树因为他的查找效率很高然后用机器扫描卡看你卡的信息是否在我的树中在就让你进 2、key/value的模型通过key找value ①、高铁刷身份证 买了票就能进站刷身份证读的是身份证号码【key就是身份证value就是票的信息】然后通过身份证到后台服务器查是否有票的信息是否是这个车站这个车次等等即通过身份证找value ②、中英文互译 中文就是key英文就是value即通过中文找英文或通过英文找中文。 ③、统计次数 统计次数即通过一个值找另一个值用搜索树实现的原因是二叉搜索树的效率高搜索快 key/value模型的实现只需在我们实现的二叉搜索树中改动一下代码即可即节点里面除了有key还有value但是比较大小的过程还是用key来比较和value没关系找到了key就相当于找到了value因为两者在同一节点中还要修改的就是Find函数返回值变成返回节点的指针而不是bool值因为这样返回的节点既有key又有value 注意 对于搜索树的修改搜索树中key是不允许修改的 如果是kv模型的搜索树可以修改value但不能修改key就是因为你改了key就不一定满足二叉搜索树的条件了 kv模型的完整代码
BSTree.hpp :
//key/value模型
#includeiostream
#includestring
using namespace std;templateclass K, class V
struct BSTreeNode
{BSTreeNode(const K key,const V value):_key(key),_value(value), _left(nullptr), _right(nullptr){}BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _value;};
templateclass K, class V
class BSTree //Binary Search Tree
{typedef BSTreeNodeK,V Node;
public:bool Insert(const K key, const V value){if (_root nullptr){//若为空树就给它一个节点_root new Node(key, value);//new是开空间初始化所以要调用构造函数你要写的return true;}Node* cur _root;//从根节点开始比较Node* parent nullptr;while (cur){//都会找一个空位置插入不会说挪动节点来进行插入if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//若在走的过程中遇到相同的数据返回假这个数据无法插入return false;}}cur new Node(key,value);//向这个空位置插入数据//利用parent的位置与cur连接if (parent-_key key)parent-_left cur;//比根节点小链接到左边elseparent-_right cur;//比根节点大链接到右边return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return cur;//说明相等则找到了返回真}}return nullptr;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//找到了开始删除//1.左为空if (cur-_left nullptr){if (cur _root)_root cur-_right;else{if (parent-_left cur)parent-_left cur-_right;//cur在父亲的左边就让父亲的左指向cur的左elseparent-_right cur-_right;//cur在父亲的右边就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root)_root cur-_left;else{if (parent-_right cur)parent-_right cur-_left;//cur在父亲的右边就让父亲的右指向cur的左elseparent-_left cur-_left;//cur在父亲的左边就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent cur;Node* Rightmin cur-_right;//若用右树的最小节点即右树最左节点while (Rightmin-_left){//最左节点的左子树一定为空故为判断条件parent Rightmin;//替换节点不一定是叶子结点故还要用parent来链接Rightmin Rightmin-_left;}cur-_key Rightmin-_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树则父亲的右指向它的右//若它是parent的左子树则父亲的左指向它的左if (Rightmin parent-_left)parent-_left Rightmin-_right;elseparent-_right Rightmin-_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到则该数据不存在}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 testTree1()
{BSTreestring, stringdict;//字典dict.Insert(sort, 排序);dict.Insert(polynomial, 多项式);dict.Insert(femininity, 女性);string str;while (cin str){BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_value endl;}else{cout 无此单词 endl;}}
}void testTree2()
{string strArr[] { 西瓜,西瓜,香蕉,樱桃,西瓜,西瓜,香蕉 };BSTreestring, int countTree;//key是stringvalue是intfor (auto str : strArr){BSTreeNodestring, int* ret countTree.Find(str);if (ret nullptr){//第一次出现就插入这个水果出现一次,因为一开始树为空countTree.Insert(str, 1);}else{//出现过了就次数ret-_value;}}countTree.InOrder();
} Test.cpp
#includeBSTree.hppint main()
{//testTree1();testTree2();return 0;
}
key/value的应用场景
应用场景1--中英文互译
key/value模型测试下面代码逻辑中英文互译 应用场景2--统计水果出现次数
有一堆水果请你统计水果出现的次数 四、二叉搜索树性能分析 如果插入的数据是有序的或者接近有序的那么搜索树效率就完全没办法保障 如1 2 3 4 5 6 7 8对于树就变成了单支树搜索树的效率最坏的情况下是ON 如何解决平衡树1、AVLTree 2、红黑树
