【C++】---二叉搜索树
【C++】---二叉搜索树
- 一、二叉搜索树概念
- 二、二叉搜索树操作（非递归）
- 1.二叉搜索树的查找 （非递归）
- （1）查找
- （2）中序遍历
- 2.二叉搜索树的插入（非递归）
- 3.二叉搜索树的删除（非递归）
- 三、二叉搜索树操作（递归）
- 1.二叉搜索树的查找（递归）
- 2.二叉搜索树的插入（递归）
- 3.二叉搜索树的删除（递归）
- 四、二叉搜索树的默认成员函数
- 1.构造
- 2.拷贝构造
- 3.赋值运算符重载
- 4.析构
- 五、K模型和KV模型搜索树
- 1.K模型搜索树
- 2.KV模型搜索树
- 六、二叉搜索树性能分析
一、二叉搜索树概念
二叉搜索树又叫二叉排序数，它或者是空树，或者是具有以下性质的二叉树：
- 如果它的左子树不为空，那么左子树上所有节点的值都小于根结点的值。
- 如果它的右子树不为空，那么右子树上所有节点的值都大于根节点的值。
- 它的左右子树也是二叉搜索树。
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};比如说：这个数组都可以将它化为二叉搜索树
总结：在左子树值比根小，右子树值比根大。 当树走中序遍历时，序列都是有序的。
二叉搜索树 的 结构定义：
#include using namespace std; template struct BSTreeNode { BSTreeNode* _left; BSTreeNode* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) { } }; template class BSTree { typedef BSTreeNode Node; private: Node* _root; public: BSTree() :_root(nullptr) { } };二、二叉搜索树操作（非递归）
1.二叉搜索树的查找 （非递归）
利用二分查找的方法，借助我们去二叉搜索树中查找节点。
查找的时间复杂度：最坏的情况，就是查找高度（h=logN）次，就可以判断一个值在不在节点里面。
（1）查找
查找的思路：
- key比当前结点的值小，往左走！
- key比当前结点的值大，往右走！
- key==当前结点的值，就找到了！
// 查找： Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key _key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return cur;// 找到了！ } } return nullptr;// 遍历完了，都还没找到！ }（2）中序遍历
由于根节点_root是私有成员变量，如果在main函数里面来进行中序遍历的话，这就是在类外对私有成员进行访问，这是不合法的！
所以说我们要解决这个问题，可以用这样：
在类的public内的 中序遍历 InOrder 里面 再套一层私有的中序遍历：_InOrder，这样，_InOrder身为私有函数，就可以访问：私有变量_root！
private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout _key _right); } public: // 中序遍历： void InOrder() //这个函数 类外可以直接访问！ { _InOrder(_root); // 这个函数，是 私有函数 对 私有成员 的访问！ cout if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; // (1) 找到插入的位置 while (cur) { if (key _left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false;// 二叉搜索树不允许数据冗余！ } } cur = new Node(key); // (2) 判断 if (key_key) { parent->_left = cur; } else { parent->_right = cur; } return true; }3.二叉搜索树的删除（非递归）
非递归删除：
（1）找位置
①key比当前节点值大，向左走 ②key比当前节点值小，向右走 ③key等于当前节点值，找到了，准备删除（2）删除，有两种删除方法：非递归和递归
非递归删除: ①该节点没有孩子，即该节点是叶子节点，删除节点后把父亲指向自己的指针置空
②该节点有一个孩子，就把该节点的孩子节点的链接给该节点的父亲，顶替自己的位置， ①可以当成②的特殊情况
③该节点有两个孩子，找比它自己的左孩子大，比它自己的右孩子小的节点替换它 （也就是拿它的左子树的最大节点或右子树的最小节点替换它）， 替换之后，该节点就只有一个孩子或没有孩子了，就变成①或②了。
// 删除 bool erase(const K& key) { Node* cur = _root; Node* parent = nullptr; // (1) 找到插入的位置 while (cur) { if (key _key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { break; } } // 1、2、 (子 代替 父亲的位置) // 大前提：如果要删除的节点，left为空 if (cur->_left == nullptr) { // 如果要删除根！ if (cur == _root) { _root = cur->_right;// 那就让cur的右当根 } // 如果要删除的不是根！ else { // 如果要删除的节点cur，在父亲的左边。 // 因为是替代法，所以说要让 子 的位置代替 父亲 的位置，但是 子 的位置只有_right存在，所以说会把_right的位置放到即将要删除cur的位置。 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } // 大前提：如果要删除的节点，right为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { // 因为是替代法，所以说要让 子 的位置代替 父亲 的位置，但是 子 的位置只有_left存在，所以说会把_left的位置放到即将要删除cur的位置。 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } // 3、要删除的cur不只有一个节点。可能有多个节点，甚至整个指子树 // 找到要删除节点cur，左子树最大的节点，右子树最小的节点，来代替cur的位置。 else { // 要么找cur左子树中的max，要么就找右子树中的min // 这里 以 RightMin为例！ // (1)找到 RightMin (就像找 cur那样) Node* RightMin = cur->_right; Node* RightMinParent = cur; // 定义 RightMinParent 为了方便后续节点的连接。 while (RightMin->_left) { RightMinParent = RightMin; RightMin = RightMin->_left; } // (2)找到了 就交换！ swap(RightMin->_key, cur->_key); // (3) 交换完后 就链接！ if (RightMinParent->_left == RightMin) RightMinParent->_left = cur; else RightMinParent->_right = cur; // 链接完成！ delete cur; } return true; }递归删除：
相对于非递归，只需要修改找到了要修改的代码：找到了后不需要管cur到底左为空、右为空、还是左右都不为空
① 找要删除节点的右子树的最小节点并把它的值保存起来
② 删除右子树的最小节点
③ 把要删除的节点值替换成右子树的最小节点值
else//左右都不为空，替换法删除 { //找右子树最小节点 Node* minRight = cur->_right; while (minRight->_left) { minRight = minRight->_left; } //用min保存右子树最小节点的值 K min = minRight->_key; //递归调用自己去替换删除节点，一定会走到左为空的情况处理 this->Erase(min); //删除完毕替换节点之后，把cur的值替换成min cur->_key = min; }三、二叉搜索树操作（递归）
理解了非递归操作以后， 递归操作就很简单了：
#include using namespace std; //树的节点可以支持多种类型 template //树节点结构 struct BSTreeNode { BSTreeNode* _left;//左指针 BSTreeNode* _right;//右指针 K _key;//值 //构造函数 BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} }; template class BStree//树结构 { typedef BSTreeNode Node; public: //递归查找 Node* FindR(const K& key) { return _FindR(_root, key); } //递归插入 bool InsertR(const K& key) { return _InsertR(_root, key); } //递归删除 bool EraseR(const K& key) { return _EraseR(_root, key); } private: Node* _root; };由于_root是私有的，可以把递归子函数查找、插入、删除都定义成私有的
1.二叉搜索树的查找（递归）
private: //查找 Node* _FindR(Node* root, const K& key) { if (root == nullptr)//没找到 { return nullptr; } if (key _key)//到左子树去找 { FindR(root->_left, key); } else if (key > root->_key)//到右子树去找 { FindR(root->_right, key); } else//找到了 { return root; } }2.二叉搜索树的插入（递归）
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 bool _InsertR(Node*& root, const K& key) { if (root == nullptr)//找到位置了 { root = new Node(key); return true; } if (key _key)//到左子树去找位置 { _InsertR(root->_left, key); } else if (key > root->_key)//到右子树去找位置 { _InsertR(root->_right, key); } else//已存在，无需插入 { return false; } }3.二叉搜索树的删除（递归）
递归删除：和二叉树的删除（非递归）一样，找到后的删除也有两种方式，递归和非递归
找到后的非递归删除：
//插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 bool _EraseR(Node*& root, const K& key) { if (root == nullptr)//没找到 { return false; } if (key _key)//到左子树去找 { _EraseR(root->_left, key); } else if (key > root->_key)//到右子树去找 { _EraseR(root->_right, key); } else { //找到了，root就是要删除的节点 if (root->_left == nullptr)//root左为空 { Node* del = root; root = root->_right; delete del; } else if (root->_right == nullptr)//root右为空 { Node* del = root; root = root->_left; delete del; } else//root左右都不为空 { //找到右子树最左节点替换 Node* minParent = root; Node* minRight = root->_right; while (minRight->_left) { minParent = minRight; minRight = minRight->_left; } //保存替换节点的值 cur->_key = minRight->_key; //链接 if (minParent->_left == minRight) { minParent->_left = minRight->_right; } else { minParent->_right = minRight->_right; } //删除 delete minRight; } return true; } }找到后的递归删除：
else//root左右都不为空 { //找右子树最左节点 Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } //保存右子树最左节点的值 K min = minRight->_key; //使用递归方法删除右子树最左节点 _Erase(root->_right, min); }四、二叉搜索树的默认成员函数
现在还剩下二叉搜索树的构造、拷贝构造、赋值运算符重载、析构函数。
1.构造
public: //构造函数需要将根初始化为空就行了 BSTree() :_root(nullptr) {}2.拷贝构造
拷贝构造利用递归调用子函数不断拷贝节点:
//拷贝构造 BSTree(const BSTree& t) { _root = t.copy(t._root); }在子函数处:
Node* _copy(Node* root) { if (root == nullptr)//如果根为空，直接返回 { return; } Node* copyNode = new Node(root->_key);//创建根节点 copyNode->_left = _copy(root->_left);//递归拷贝左子树节点 copyNode->_right = _copy(root->_right);//递归拷贝右子树节点 return copyNode;//返回根 }3.赋值运算符重载
借助拷贝构造用现代写法写:
//赋值运算符重载(现代写法) BSTree& operator=(const BSTree& t) { swap(_root,t._root); return *this; }4.析构
递归调用子函数去析构
//析构 ~BSTree() { _Destroy(_root); _root = nullptr; }在子函数处:
_Destroy(root) { if (root == nullptr) { return; } _Destroy(root->_left); _Destroy(root->_right); delete root; }五、K模型和KV模型搜索树
1.K模型搜索树
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
1、以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
2、在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2.KV模型搜索树
KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：
1、比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
2、再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是就构成一种键值对。
改造二叉搜索树为KV结构的代码
#pragma once #include #include using namespace std; namespace key_value { template struct BSTreeNode { BSTreeNode* _left; BSTreeNode* _right; K _key; V _value; // pair _kv; BSTreeNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; template class BSTree { typedef BSTreeNode Node; public: // logN 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 _right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key _right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key _right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return cur; } bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key _right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { // 删除 // 左为空，父亲指向我的右 if (cur->_left == nullptr) { //if(parent == nullptr) if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { //if(parent == nullptr) if (cur == _root) { _root = cur->_left; } else { // 右为空，父亲指向我的左 if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else { // 左右都不为空，替换法删除 // // 查找右子树的最左节点替代删除 Node* rightMinParent = cur; Node* rightMin = cur->_right; while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } swap(cur->_key, rightMin->_key); if (rightMinParent->_left == rightMin) rightMinParent->_left = rightMin->_right; else rightMinParent->_right = rightMin->_right; delete rightMin; } return true; } } return false; } void InOrder() { _InOrder(_root); cout if (root == nullptr) { return; } _InOrder(root-_left); cout _key
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
