国外网页模板网站,怎么做wep网站,长春网页设计培训,wordpress 手机登录A:你长大后想要做什么#xff1f; B:写下“快乐”…… A:不#xff0c;你理解错我的意思了#xff0c;我是说 B:不#xff0c;是你理解错了人生…… 文章目录一、二叉搜索树的实现1.struct TreeNode{}2.迭代版本2.1 Insert()插入结点#xff08;解决链接的问题#xff09…A:你长大后想要做什么 B:写下“快乐”…… A:不你理解错我的意思了我是说 B:不是你理解错了人生…… 文章目录一、二叉搜索树的实现1.struct TreeNode{}2.迭代版本2.1 Insert()插入结点解决链接的问题2.2 Find()查找结点2.3 Erase()删除结点3.递归版本3.1 InOrder()中序遍历3.2 Insert()插入结点解决链接的问题3.3 Find()查找结点3.4 Erase()删除结点交换后整体不是搜索树但结点的右子树是搜索树呀4.二叉搜索树的成员函数4.1 构造函数拷贝构造被编译器认为是构造函数4.2 析构函数4.3 拷贝构造4.4 赋值重载二、K模型和KV模型1.key模型2.key value模型一、二叉搜索树的实现
1.struct TreeNode{}
1. 搜索树的结点的定义也比较简单每个结点都有左右子树和自身存储的_key值_key就是利用搜索树进行搜索时的数据。
template class K
struct TreeNode
{TreeNode(const K val):_key(val), _left(nullptr), _right(nullptr){}K _key;TreeNodeK* _left;TreeNodeK* _right;
};2.迭代版本
2.1 Insert()插入结点解决链接的问题
1. 在插入结点时要保证大于根节点的结点插入到右子树小于的插入到左子树这样才满足二叉搜索树的定义当根节点为空的时候我们要单独处理这种情况new一个树结点当前这个树节点就是根。
2. 在cur向下迭代寻找插入位置的过程中只要遇到了nullptr则当前cur所指向的结点即为要插入的结点位置但如果你直接new一个结点将结点地址给到cur指针这是一点用都没有的因为你仅仅将结点地址给了一个局部变量外面树的结点的链接关系并没有发生变化插入结点必须让cur的父节点和cur进行链接这才算在树里面插入了结点所以我们需要一个parent指针用于指向cur所指结点的父节点等到cur到达插入位置时我们让parent的左或右指针指向新new出来的也就是要插入的结点。 那到底是parent的左还是右呢这个时候需要比较一下parent的key和插入结点val的大小val大那就插入到parent的右指针val小那就插入到parent的左指针。
3. 普通的二叉搜素树不允许树中有两个相同的值出现所以如果插入的值和树中的值相同时此时我们认为插入失败返回false
bool Insert(const K val)
{if (_root nullptr){_root new Node(val);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (val cur-_key){parent cur;cur cur-_right;}else if (val cur-_key){parent cur;cur cur-_left;}elsereturn false;}// cur new Node(val);//让局部指针cur指向新开辟结点有什么用对搜索树一点影响都没有你需要改变搜索树的链接关系。if (val parent-_key)parent-_right new Node(val);elseparent-_left new Node(val);return true;
}2.2 Find()查找结点
1. 想要在二叉搜索树里面查找一个结点那简直太简单了我们只要依次比较根节点和val的大小就可以val大去右子树查找val小去左子树查找直到val和_key值相等时查找成功返回true如果cur都已经查找到nullptr了那么说明这棵树中没有val值的结点返回false 能如此轻松查找到对应的结点本质还是因为二叉搜索树结构的优势所在他的结构天生就是为搜索海量的数据而生。
bool Find(const K val)
{Node* cur _root;while (cur){if (val cur-_key){cur cur-_right;}else if (val cur-_key){cur cur-_left;}elsereturn true;}return false;
}2.3 Erase()删除结点
1. 如果我们要删除搜索树的结点时如果细分可分为下面三种情况但12两种情况在删除时其实可以算作一种这样的结点删除的方法我们称之为托孤行为指的是如果删除结点的左右孩子个数为0或1时我们可以让其父结点指向删除结点的非空结点也就是将删除结点的孩子托付给父节点这样的结点我们直接删除即可。
2. 对于左右均不为空的结点删除时我们采用交换法进行删除即去根结点的右子树找最小结点或者去左子树找最大结点进行和根结点值的交换只有这样替换后排除被交换结点外其余结点还能继续满足二叉搜索树调用Erase()删除接口后树依旧可以是二叉搜索树。 而交换之后我们只需要删除被交换的结点就好了此时还需要一个被交换结点的parent指针让parent指向被交换结点的非空子节点如果子结点均为空则随便指向一个就好我们通过if else语句就可以实现。 3. 上面所说的都是思路下面来看看用代码究竟该如何实现对于直接删除法普通结点直接托孤即可先判断普通结点是父亲的左还是右判断之后让父亲的左或右指向普通结点的非空子节点即可。但对于根节点删除时情况有些特殊因为托孤的时候parent用nullptr初始化若此时访问parent的左或右则会发生空指针访问所以此时我们不再选择托孤直接将根节点挪动到其非空子节点即可。 4. 对于交换法删除就比较麻烦了我们要先去找cur的右子树的最小结点然后将minRight和cur的值进行交换最后直接删除minRight即可直接删除肯定也是需要minParent的但在定义minParent时也是有讲究的如果用nullptr初始化minParent的话上面这种情况不会发生问题因为minParent会被迭代到一个不为空的结点位置但如果是下面这种情况minRight恰好是cur的右子树根如果此时直接托孤就会发生空指针的访问所以在初始化minParent时我们用cur来初始化。 在链接的时候也需要分情况来看待如果minRight恰好是cur的right那么直接让minParent的右链接到minRight的右也就是第二种情况。如果minRight不是cur的right那么我们直接让minParent的左指向minRight的右即可因为最左结点minRight的左一定为空但右不一定为空所以托孤时要让minParent的左指向minRight的右。也就是第一种情况。 bool Erase(const K val)
{Node* cur _root;Node* parent nullptr;while (cur){if (val cur-_key){parent cur;cur cur-_right;}else if (val cur-_key){parent cur;cur cur-_left;}else//找到要删除的结点了{if (cur-_left nullptr){if (cur _root)//删除结点是根节点{_root cur-_right;}else if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;delete cur;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;delete cur;}else{Node* minParent cur;//minParent如果是nullptr则当cur-_right是最小结点时会发生空指针访问Node* minRight cur-_right;//找右子树最小结点 或者 左子树最大结点while (minRight-_left){minParent minRight;minRight minRight-_left;}swap(cur-_key, minRight-_key);if (minRight cur-_right)minParent-_right minRight-_right;//右子树最小结点的左节点一定为空让父节点链接其右结点即可。elseminParent-_left minRight-_right;delete minRight;}return true;}}return false;
}3.递归版本
3.1 InOrder()中序遍历
1. 递归版本的中序遍历那都是老熟人了只要先去遍历左树到nullptr的时候返回然后输出root的值最后再去遍历一下右树即可。也就是暴力法递归将整棵树的每一个结点按照中序遍历一遍。
2. 但这里有一个关于类和对象知识的小技巧在遍历的时候我们肯定需要根节点_root但如果直接暴露根节点到class BSTree{}外面就破坏了类的封装性因为外面想要传参_root就必须提供公有的访问根节点的函数类封装自然就被破坏了所以我们将_InOrder搞成私有外面的公有InOrder调用私有_InOrder在公有函数中完成根节点的传参。 很多需要传根节点的公有函数都是这样做的即把核心接口封装成私有在公有接口中传根节点_root void InOrder(){return _InOrder(_root);}
private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}Node* _root nullptr;3.2 Insert()插入结点解决链接的问题
1. 无论是递归插入结点还是非递归我们都需要处理结点和父节点链接的问题所以有一个比较好的思路就是在递归查找插入位置的过程中我们并不是找到那个位置让父节点去链接那个位置而是判断遍历到的结点的左或右是否为空如果为空并且满足插入结点的位置那么直接链接即可。这个思路不再像上面思路中让parent链接插入结点位置而是先不着急处理链接先判断root的右或左是否为插入结点的位置如果是那就插入如果不是那就继续递归向下寻找。 但这种思路有一个问题无法处理那就是空树的情况有人说空树还不好处理吗你直接new一个结点将这个结点的地址给到形参root不就可以了吗道理确实是这样的但无法做到因为root是一个形参变量你将new出来的结点的地址给一个形参变量函数外面的_root成员变量还是无法改变的所以如果形参是普通的指针则无法处理空树的情况。这个道理其实就是上面判断root的左或右的问题因为我们无法直接处理形参root当前指向的结点因为root是形参外面搜索树的实际结点无法被操纵但我们可以处理root的左或者右这个左或者右指向的就是外面搜索树的结点的左或者右 2. 所以上面的思路再好再清奇也无法处理空树的情况本质还是因为形参变量无法处理当前结点树外面的当前结点始终不受影响。 但如果我们不用普通形参呢我们用指针的引用呢这就非常的牛了我们可以直接操纵函数外面的二叉搜索树本身这个时候递归插入结点就非常非常简单了只要找到插入的位置也就是rootnullptr的时候我们直接new结点将结点地址给到root这样就完成结点插入了因为此时是引用无论改变哪个结点的地址外面的搜索树都会被影响如果root没到nullptr那就递归向下查找即可注意此时也不是暴力递归查找还是通过key和val的大小来递归向下查找这样的效率更高。 bool InsertR(const K val){return _InsertR(_root, val);}
private:bool _InsertR(Node* root, const K val)//你如果不用引用那这里就是临时的形参栈帧外面什么都影响不了{if (root nullptr){root new Node(val);return true;}if (val root-_key)return _InsertR(root-_right, val);else if (val root-_key)return _InsertR(root-_left, val);elsereturn false;}/*bool _InsertR(Node* root, const K val)//一个比较不错的思路但是对于空树不太实用{if (root nullptr){}if (root-_key val)return false;if (val root-_key){if (root-_right nullptr){root-_right new Node(val);return true;}else{_InsertR(root-_right, val);}}else{if (root-_left nullptr){root-_left new Node(val);return true;}else{_InsertR(root-_left, val);}}}*/3.3 Find()查找结点
1. 递归查找子节点那也是非常简单的和插入结点的递归道理相同我们不采用暴力递归的方式而是用搜索树的结构特征进行查找val大去右面递归查找val小去左面递归查找直到key和val相等的时候我们返回true表示查找成功如果查找到nullptr则表示查找失败返回false即可 bool FindR(const K val){return _FindR(_root, val);}
private:bool _FindR(Node* root, const K val){if (root nullptr)return false;if (root-_key val)return true;else if (root-_key val)return _FindR(root-_right, val);elsereturn _FindR(root-_left, val);//return _FindR(root-_left, val) || _FindR(root-_right, val);//暴力查找就完事了}3.4 Erase()删除结点交换后整体不是搜索树但结点的右子树是搜索树呀
1. 递归删除结点的实现我们采用引用结构体指针作为形参引用总是能带来很多的好处直接操纵搜索树的结点何乐而不为呢 思路不变利用搜索树的结构先进行删除结点的递归查找等递归找到删除结点后还是老套路需要分情况进行删除对于直接删除的情况这回只需要让他的非空子节点地址覆盖掉当前删除结点地址就够了这样就完成了托孤行为这正是引用带来的好处。但覆盖之后不要忘记释放删除结点的空间所以我们用一个临时指针记录一下删除结点的地址在非空子节点地址覆盖掉删除结点地址之后我们在delete临时指针指向的空间。 利用引用对于根节点的删除情况也可以适用因为我们不再需要parent直接用非空子节点覆盖删除结点的地址就可以所以即使对于删除根节点的情况引用的方式依旧可以适用。
2. 而对于交换法删除的情景来说我们可以利用递归将问题进行转换虽然交换之后整体不再满足搜索树但删除结点的右子树依旧满足搜索树所以我们只要递归删除其右子树就可以将交换法删除的问题通过递归右子树再次转换为直接删除的问题完美进行代码复用。 bool EraseR(const K val){return _EraseR(_root, val);}
private:bool _EraseR(Node* root, const K val){if (root nullptr)return false;if (val root-_key){return _EraseR(root-_right, val);}else if (val root-_key){return _EraseR(root-_left, val);}else{if (root-_left nullptr)//用引用删除单链的根节点时不用去找父亲直接修改当前结点就可以{Node* tmp root;root root-_right;delete tmp;}else if (root-_right nullptr){Node* tmp root;root root-_left;delete tmp;}else{//这里的解决方法有两种一种是直接cv上面的解决方式一种是通过递归将问题转换为直接删除。Node* minRight root-_right;//找右子树最小结点 或者 左子树最大结点while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);_EraseR(root-_right, val);//虽然整体不是搜索树了但是root的右子树在交换之后还是搜索树可以用直接删除。}return true;}}4.二叉搜索树的成员函数
4.1 构造函数拷贝构造被编译器认为是构造函数
1. 搜索树的构造函数实际并不用写利用C11提供的缺省值和编译器默认生成的构造函数就可以完成搜索树的初始化但如果我们写了树的拷贝构造函数那就不得不写出构造函数了因为拷贝构造也是构造但拷贝构造需要传参我们在初始化树的时候不会提供任何参数所以此时就会报错没有合适的默认构造可用。 因为在我们写了拷贝构造之后编译器不会生成默认的拷贝构造了所以这个时候就必须我们自己来写无参的默认构造。
2. 如果要写也非常简单只要将指向根节点的指针初始化为nullptr就好了在Insert()插入结点构造搜索树的时候我们会处理根为nullptr的情况。
template class K
class BSTree
{typedef TreeNodeK Node;
public:BSTree():_root(nullptr){}//BSTree(const BSTreeK t)//树的拷贝构造类型是自定义类型//{//可以层序遍历然后将遍历到的数Insert构建一棵新的树。//_root Copy(t._root);//}
private:Node* _root nullptr;
}; 4.2 析构函数
1. 搜索树的析构函数我们可以采用后序遍历的方式将结点进行释放因为一旦析构根节点他的左右孩子我们就找不到了所以按照左右根的顺序来释放结点遇到空结点就返回因为空结点指针指向的是空并未分配堆的有效空间所以无须操作空结点指针等待栈帧销毁时自动清理这些局部变量即可。
~BSTree()
{Destroy(_root);_root nullptr;
}
void Destroy(Node* root)
{if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;
}4.3 拷贝构造
1. 搜索树的拷贝构造即为重新构造出一棵与原树相同的树我们肯定采取递归的方式来进行树的构建所以写一个子函数Copy(Tree Node* root)将原树的根节点传过去然后我们按照构建根结点构建左子树构建右子树的方式进行二叉搜索树的构建构建根节点的同时要进行左右子树的链接过程大家好好体会递归过程。
BSTree(const BSTreeK t)//树的拷贝构造类型是自定义类型
{//可以层序遍历然后将遍历到的数Insert构建一棵新的树。_root Copy(t._root);}
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;
}4.4 赋值重载
1. 写完拷贝构造再写赋值重载就简单的多了我们利用形参的临时拷贝然后进行根节点的交换即可完成搜索树的赋值重载由于形参在离开函数栈帧时会被自动销毁对于自定义类型会自动调用析构函数所以不用担心内存泄露的发生。
BSTreeK operator(const BSTreeK t)
{swap(_root, t._root);// 交换之后不用担心内存泄漏因为形参对象离开函数栈帧会自动调用其析构函数析构的是原来this指向的旧对象//拷贝构造出来的新内容已经交换到this手上了不用担心内存泄漏。return *this;
}二、K模型和KV模型
1.key模型
1. K模型即为二叉搜索树中只存储一个_key值K模型中只有key作为关键码关键码即为需要搜索的值。
2. K模型的适用场景之一便是考虑在不在的问题比如判断某个作家写的书中的单词是否合法我们可以将词库中的单词作为_key值存储到搜索树里面然后去搜索树中进行查找判断当前的单词是否存在于搜索树中单词作为string当然是可以比较大小的所以我们只要定义出BSTree string T的对象即可搜索的效率在logN到N之间。 另一种较为常见的场景是学生出入系统车库出入系统等都需要判断对应的对象是否存在例如不是本校的学生不能刷卡进入校园不是车库中的车杆子不会抬起放入这些都是判断在不在的情形这样的情景我们称之为K模型。
2.key value模型
1. 另一种更为常见的模型是key value模型即通过key关键码去查找与之对应的值value即Key, Value的键值对比如英汉互译统计所给单词出现的次数统计水果出现的次数他们的键值对分别是string, stringstring, intstring, int。
2. 下面便是KV模型下搜索树结点的定义在比较和构建搜索树时我们都是用关键码_key来进行比较找到key后通过key对应的结点地址当然可以轻松拿到对应的value值。 将K模型搜索树改造成KV模型代码也是非常简单的只需要在树结点的结构体里面增加一个变量即可 树的模板中多增加一个value的类型V其余部分都不用变因为比较的逻辑都没有变仅仅只是在结点里面多加了一个value值而已。
3. 例如英汉互译这样的场景我们简单的在树中插入几个结点然后判断输入的str是否在树里面如果Find()查找到的话那就通过Find()的返回结点地址输出结点对应的value值即可。 确定水果出现的次数也比较简单如果水果存在于二叉搜索树那就将水果的value值value代表出现次数1如果不存在那就插入结点结点的value初始值设定为1即可。
namespace KV
{template class K, class Vstruct TreeNode{TreeNode(const K key, const Vvalue)//每一个结点里面既有_key又有_value:_key(key),_value(value), _left(nullptr), _right(nullptr){}K _key;V _value;TreeNodeK,V* _left;TreeNodeK,V* _right;};//BSTreestring, vectorstring bookInfotemplate class K, class Vclass BSTree{typedef TreeNodeK, 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 (key cur-_key){parent cur;cur cur-_right;}else if (key cur-_key){parent cur;cur cur-_left;}elsereturn false;}// cur new Node(val);//让局部指针cur指向新开辟结点有什么用对搜索树一点影响都没有你需要改变搜索树的链接关系。if (key parent-_key)parent-_right new Node(key, value);elseparent-_left new Node(key, value);return true;}Node* Find(const K key)//返回树的结点结点里面有key和value{Node* cur _root;while (cur){if (key cur-_key){cur cur-_right;}else if (key cur-_key){cur cur-_left;}elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}Node* _root nullptr;};
}void TestBSTree4()//测试KV模型
{// 将词库中的单词都放进这棵搜索树中单词string之间是可以比较大小的只要单词合法则一定能在搜索树中找到对应的string。// Key模型判断在不在// 场景检查单词拼写是否正确/车库出入系统/……//K::BSTreestring dict;//Key/Value的搜索模型通过Key查找或修改Value// 场景1经典的英汉互译KV::BSTreestring, string dict;//value还可以是一颗搜索树但如果数据量特别小的话没必要用搜索树存用vector就够了dict.Insert(apple, 苹果);dict.Insert(banana, 香蕉);dict.Insert(pear, 鸭梨);dict.Insert(watermelon, 西瓜);string str;while (cinstr){//KV::TreeNodestring, string* ret dict.Find(str);auto ret dict.Find(str);if (ret)cout ret-_value endl;elsecout 无此单词 endl;}// 场景2统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 ,草莓};//统计次数这样的场景非常适合二叉搜索树或者哈希的方式来解决。尤其是你想通过一个值去找另一个值都可以用key value模型解决KV::BSTreestring, int countT;for (auto e : arr){auto* cur countT.Find(e);//没有找到返回nullptrif (cur nullptr)countT.Insert(e, 1);elsecur-_value;}countT.InOrder();
}
