搜索二叉树BSTree的原理及实现
目录
一、简介
二、功能的实现
节点的实现
这里为什么模板参数采用的是K而不是T呢？
树体的实现
非递归版本
Insert函数
Find函数
Erase函数
递归版本
中序遍历
FindR
InsertR
EraseR
构造函数
析构函数
拷贝构造
赋值重载
一、简介
BSTree（Binary Search Tree），即二叉搜索树，是一种特殊的二叉树，具有以下特性：
-
节点的左子树上所有节点的值均小于它的根节点的值：这意味着在二叉搜索树中，任何一个节点的左子树中的元素都是小于该节点的。
-
节点的右子树上所有节点的值均大于它的根节点的值：同样，任何一个节点的右子树中的元素都是大于该节点的。
-
左右子树也分别为二叉搜索树：二叉搜索树的每一个子树也是二叉搜索树。
-
没有键值相等的节点：在二叉搜索树中，所有节点的值都是唯一的。
二叉搜索树具有以下优点：
-
高效的查找、插入和删除操作：在二叉搜索树上进行查找、插入和删除操作的时间复杂度平均为O(log n)，其中n是树中节点的数量。
-
保持数据的有序性：二叉搜索树的中序遍历结果是有序的，即按照从小到大的顺序排列。
二叉搜索树的操作包括：
-
查找：从根节点开始，比较当前节点与目标值的的大小，根据比较结果决定是向左子树还是右子树递归查找。
-
插入：从根节点开始，比较当前节点与待插入值的大小，找到合适的位置插入新节点。
-
删除：删除操作较为复杂，需要考虑三种情况：
- 删除的节点是叶子节点，可以直接删除。
- 删除的节点只有一个子节点，可以用其子节点代替该节点。
- 删除的节点有两个子节点，通常找到该节点的中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点）来代替，然后删除该后继或前驱节点。
下图就是一棵根据数组建成的搜索二叉树
下面我们就根据搜索二叉树的特点及功能进行二叉树的实现
二、功能的实现
跟普通的树结构一样，我们需要两个自定义类型来实现BSTree的功能。首先定义一个节点，用来存放树的键位，其次另一个自定义类型进行树功能接口的实现和树的搭建。
在这里我们并没有单独的放到一个命名空间中，主要是因为跟std的命名冲突不大，所以我们直接在全局就可以进行实现。
节点的实现
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left; //模板实例化之后才是类型BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};
由于我们希望节点部分对于整个树部分是公开的希望可以访问他的_left等内容，所以我们采用struct结构，而不是class类。
需要注意的是 BSTreeNode<K>*模板实例化之后才是类型。
这里为什么模板参数采用的是K而不是T呢？
以下是使用K作为模板参数的几个原因：
明确性：K暗示了模板参数代表的是键（Key），这在使用二叉搜索树时，键是用来比较和排序的主要元素。
一致性：在涉及键值对或键相关的数据结构中，使用K作为键的类型可以保持命名的一致性，使得代码在不同的上下文中易于理解和维护。
约定：在许多编程实践中，T通常用于表示“Type”，是一个通用的类型占位符。但在特定的情况下，使用更具体的字母可以提供更多的上下文信息。例如，V可能用于表示“Value”，E可能用于表示“Element”等。
避免混淆：如果代码中已经使用了T作为其他意义下的模板参数，为了避免混淆，可能会选择其他字母。
总的来说，选择K而不是T是为了更好地传达模板参数的意图，并且遵循了类型参数命名的通用约定。这样的命名习惯有助于其他开发者快速理解代码的结构和用途。
树体的实现
成员参数：
由于树是由一个个节点组成的，所以参数用一个根节点构成。
private:Node* _root = nullptr; //类内初始化，将一个根节点置空为了方便使用类型，进行一次typedef
template<class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;
功能函数的实现
功能函数重点是插入、删除、遍历、修改。由于树可以进行递归实现，因此我们实现了递归与非递归版本的实现。
非递归版本
Insert函数
用来完成插入与树的构建操作。
bool Insert(const K& key) //不允许值重复
{Node* cur = _root;Node* prev = cur; //定义prev用来进行节点的链接if (cur == nullptr) //空树_root = new Node(key); //直接对根节点进行链接，而不是新建立newnodewhile (cur) //非空树{if (key > _root->_key){prev = cur;cur = cur->_right;}else if (key < _root->_key){prev = cur;cur = cur->_left;}elsereturn false;}//cur->_key = key; //错误，cur目前是一个指向未知区域的野指针cur = new Node(key); //应该连入一个新节点//链接if (prev->_key > key)prev->_left = cur;elseprev->_right = cur;return true;
}第一部分是判断该树是不是空树。让_root指向一个新开辟的节点即可。
第二部分是找到该树的空节点。之后是借助key新建一个节点。
第三部分是判断父子的位置关系，进行数据的链接。
Find函数
用于查找数据，左树小于键值，右树大于键值。
时间复杂度：logn：接近满二叉树（完全二叉树）
n：最坏（最坏的才是时间复杂度）
bool Find(const K& key) //给值检索{Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}return false;}
Erase函数
bool Erase(const K& key){Node* cur = _root;Node* prev = cur;while (cur){if (key > cur->_key){prev = cur;cur = cur->_right;}else if (key < cur->_key){prev = cur;cur = cur->_left;}else //找到了，进行删除{ if (cur->_left == nullptr) //左孩子为空{ //当节点是根时（此时不存在父节点）if (cur == _root)_root = _root->_right;//判断父子关系if (prev->_key > cur->_key)prev->_left = cur->_right; //托孤法else if (prev->_key < cur->_key)prev->_right = cur->_right;delete cur; //最终都是删除cur，可以直接写道最后}else if (cur->_right == nullptr) //右孩子为空{ //当节点是根时（此时不存在父节点）if (cur == _root)_root = _root->_left;//判断父子关系if (prev->_key > cur->_key)prev->_left = cur->_left; //托孤法else if (prev->_key < cur->_key)prev->_right = cur->_left;delete cur;}else //左右孩子都有：替换法{// 右树的最小节点(即最左节点，最左节点一定没有左孩子，但是可能有右孩子)Node* parent = cur; //定义一个父节点去链接Node* MinRight = cur->_right; //去寻找右树最小的节点while (MinRight->_left) //在此处不可能出现根的左右都是空的情况（想删除时，前两种情况已经对此做出了处理）{parent = MinRight;MinRight = MinRight->_left;}swap(cur->_key, MinRight->_key); //本质是对键值交换if (parent->_left = MinRight) parent->_left = MinRight->_right;elseparent->_right = MinRight->_right;delete MinRight;}return true; //删除成功之后返回true}}return false;}
需要注意的是：
1.考虑root是不是需要删除的对象
2.交换时，本质是对键值的交换
3.在链接时，考虑父子的关系
递归版本
中序遍历
中序是一个递增序列（可以实现有序）
二叉树的递归都需要传入根，在外面传不合适，但是可以在内部传入。但是C++不喜欢写Get（）方法，因此需要对递归的函数进行一次封装。
void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);
}void类型不需要返回，直接及逆行递归遍历即可。
FindR
递归版本的查找
由于是bool类型，应该也有一次返回。
递归函数
bool _FindR(Node* root, const K& key)
{if (root == nullptr)return false;if (key > root->_key){_FindR(root->_right, key);}else if (key < root->_left){_FindR(root->_left, key);}elsereturn true;
}InsertR
bool _InsertR(Node*& root, const K& key) //引用传参{if (root == nullptr){root = new Node(key); //引用传参，保证_root可以链接return true;}if (key > root->_key)_InsertR(root->_right, key);else if (key < root->_key)_InsertR(root->_left, key);else //相等return false;}需要注意的是，我们需要传入的是指针的引用，因为我们需要修改一级指针。
在子问题函数中root就是上一级问题的root->_left root->_right
因此这句代码： root = new Node(key); //引用传参，保证_root可以链接
本质就是上一层的root->_left / root->_right = new Node(key)
EraseR
bool _EraseR(Node*& root, const K& key) //指针的引用可以修改一级指针{ if (root == nullptr)return false;if (key > root->_key)_EraseR(root->_right, key);else if (key < root->_key)_EraseR(root->_left, key);else //找到了，进行删除{if (root->_left == nullptr) //左孩子为空{//不需要判断父子关系（引用传参，知道root就是上一次的_left或者_right）因此不需要定义prev指针Node* del = root;root = root->_right; //根节点也可以完成删除delete del; //不能delete rootreturn true;}else if (root->_right == nullptr) //右孩子为空{Node* del = root;root = root->_left; //根节点也可以完成删除delete del; //不能delete rootreturn true;}else //左右孩子都有：替换法{Node* MinRight = root->_right;while (MinRight->_left){MinRight = MinRight->_left;}swap(MinRight->_key, root->_key);return _EraseR(root->_right, key); //左右孩子都有这种情况要递归，必须有一次return//不能传入MinRight，因为他的父亲不能链接他的孩子（目的是为了托孤）}//return true; 不需要额外返回一次}}核心逻辑：
if (root->_left == nullptr) //左孩子为空
{//不需要判断父子关系（引用传参，知道root就是上一次的_left或者_right）因此不需要定义prev指针Node* del = root;root = root->_right; //根节点也可以完成删除delete del; //不能delete rootreturn true;
}else if (root->_right == nullptr) //右孩子为空
{Node* del = root;root = root->_left; //根节点也可以完成删除delete del; //不能delete rootreturn true;
}else //左右孩子都有：替换法
{Node* MinRight = root->_right;while (MinRight->_left){MinRight = MinRight->_left;}swap(MinRight->_key, root->_key);return _EraseR(root->_right, key); //左右孩子都有这种情况要递归，必须有一次return//不能传入MinRight，因为他的父亲不能链接他的孩子（目的是为了托孤）
}第一二种情况中，不需要判断root是否为根节点，即使为跟节点，也可以完成删除。
由于是引用传参，root可以作为一级指针就可以完成节点的链接。
第三种情况中，交换的本质还是交换键值，转化成去右子树删除对应的键值（找的是右子树的最小节点）
不能直接传入MinRight，前面的传参都是root->_left这种形式，保证可以直接找到父节点进行链接，直接传入一个节点无法完成爷孙（MinRight）节点的链接。这个地方的递归要右一次return，层层return回去。
return _EraseR(root->_right, key); 也可以改为 _EraseR(root->_right, key); return true；
构造函数
BSTree() = default; //C++11
可以写成BST() {}。也可以直接让BST（） = default。这个是C++11才出现的语法，表示的意思是要求编译器为BST类生成默认的构造函数。
析构函数
~BSTree(){Destroy(_root);}void Destroy(Node*& node) //引用传参，才能让指针置空
{if (node == nullptr)return;Destroy(node->_left);Destroy(node->_right);delete node;node = nullptr; //置空，防止出现野指针
}引用传参，才能让指针置空。 后续结构析构，防止出现野指针。
拷贝构造
拷贝构造冲成员变量入手。
//this(tree)BSTree(const BSTree<K>& t){_root = Copy(t._root);}按照先序，一次new出新阶段，进行拷贝构造。
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;}赋值重载
借助拷贝构造，完成形参的传参。内部交换跟指针，让原来的指针指向tmp二叉树，tmp二叉树跟需要拷贝构造的二叉树一致。（_root知只是指针，指向了BSTree的有效空间）
出作用域，自动调用tmp的析构，销毁原来的BSTree。
BSTree<K>& operator=(const BSTree<K> tmp) //借助拷贝构造形成形参
{swap(tmp._root, _root); //两个指针的指向交换return *this; //tmp自动析构。
}