企业官网建站的流程_网络域名地址_抖音seo源码搭建_2021拉新推广佣金排行榜

1. 二叉搜索树

1.1 定义

二叉搜索树，首先是一棵二叉树，满足根结点左子树中的结点的值都小于等于根结点，根结点右子树中的结点的值都大于等于根结点，并且，整棵二叉树中的任意左右子树都满足这个条件。

以下是二叉搜索树的示例：

1.2 应用

二叉搜素树，具有便捷的搜索功能。
因为二叉搜索树中数的分布规律，所以在一棵结点数为N的二叉搜索树中查找一个数，只需要遍历二叉搜索树的层数次，即O（log n） 的时间复杂度。
但是，这是在二叉搜索树左右子树趋于对称的情况，如果二叉搜索树左右子树中结点数的失衡较大，那么时间复杂度会趋近于O（n），如下图所示：

此时，我们要减少时间复杂度，就需要对这棵失衡的二叉树进行调整，使之变为平衡二叉搜索树。

二叉搜索树，除了能用于查找之外，还可以用于排序，所以又得名二叉排序树。

利用二叉搜索树进行排序时，只需要对整棵二叉树进行中序遍历，即可得到一个升序序列。

1.3 二叉搜索树在容器中的应用

C++标准库模板库中容器map和set底层就是一棵二叉搜索树。

二叉搜素树分为key和key-value的两种情况，同时可以根据是否允许key，即键值冗余进行划分。

set对应的就是不允许键值冗余的key情况，multiset则是允许键值冗余的key情况；map是不允许键值冗余的key-value情况，multimap则是允许键值冗余的key-value情况。

2. 二叉搜索树的实现

本篇博客，讲解不允许键值冗余的key情况，相应的key-value情况就是增添一个成员变量value，对于后者，不再赘述。

至于允许键值冗余的情况，本篇博客中暂不做讲解。

二叉搜索树的实现，实质上就是实现二叉搜索树的插入、删除、查找、遍历和销毁。二叉搜索树一般不支持修改，因为贸然修改会破坏二叉搜索树的结构。

二叉树由结点构成，因此我们先定义二叉搜索树的结点，再定义二叉搜索树——在二叉搜索树中定义整棵树的根结点作为成员变量，用以管理整棵树。

	template<class T>struct BSTNode{T _key;BSTNode<T>* _left;BSTNode<T>* _right;BSTNode(int key = 0):_key(key), _left(nullptr), _right(nullptr){}};

template<class T>
class BSTree
{
public:typedef BSTNode<T> Node;//实现相关公有成员函数private:Node* _root = nullptr;
};

2.1 插入

我们要在二叉搜索树中插入一个数，首先得找到这个数应该插入的位置，即应该插入在哪个结点之后。
我们通过大小判断，如果此数大于根结点，就到右子树中；如果此数小于根结点，就到左子树中。不断循环，直至到达一个空结点，那么这个空结点的前一个结点，就是我们要插入结点的根结点。所以，在整个过程中，肯定需要用到两个变量，一个用于记录当前结点，一个用于记录当前结点的前一个结点。

明确插入在哪个结点之后，我们还需要判断，是插入到左子树中，还是插入到右子树中，这个可以通过大小比较得到。

找数应插入的位置，我们可以使用函数递归，也可以使用循环，不过函数递归的消耗一般比较大，因此我们使用循环实现。

		void Insert(const T& key){Node* ptr = new Node(key);if (_root == nullptr)_root = ptr;else{//遍历整棵二叉搜索树，找到应处位置Node* cur = _root;Node* pre = nullptr;while (cur){pre = cur;if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else//暂且不处理相等的情况return;}if (key < pre->_key)pre->_left = ptr;elsepre->_right = ptr;}}

2.2 查找

在上述插入的逻辑中，已经涵盖查找，此处不再赘述。

对于查找函数的返回值，可以返回真假，表示是否查找到该数；也可以返回地址，如果查找到，返回相应结点地址，没查找到，则返回空指针。

bool find(const T& key)
{Node* cur = _root;while (cur){if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn true;}return false;
}

2.3 遍历

二叉搜索树的遍历是中序遍历，以实现升序排序的功能。

		//二叉搜索树的中序遍历，顺序排列，二叉排序树得名之因void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){//左根右if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ' ';_InOrder(root->_right);}

由于二叉树的中序遍历需要使用递归实现，而这里的函数递归需要传参，对于私有成员变量_root，其无法在类外直接使用，因此对外的遍历接口我们实现为无参的，然后通过这个函数的子函数以实现递归。

2.4 删除

二叉搜索树的删除要分多种情况来讨论。

具体情况如下：

• 要删除的结点没有左右结点。此时直接删除该结点，并将父结点指向该结点的指针置为空即可。
• 要删除的结点有左结点，没有右结点。删除该结点，将父结点的相应指针，指向该删除节点的左结点。（可以将没有左右节点的情况归于此类种）
• 要删除的结点有右结点，没有左结点。道理同上，指向左结点改为指向右结点即可。
• 要删除的结点左右子结点均有。这种情况，我们需要找一个结点来代替该删除结点，同时不破坏整棵树的结构。满足这样条件的结点，可以是这个删除结点左子树中的最大结点，也可以是这个删除结点右子树中的最小结点。找到这个满足条件的结点后，我们只需要将此结点的key与待删除结点的key交换，交换后，这个原本满足条件的结点就变为了我们此时要删除的结点。而这个结点的位置，要么是之前待删除结点左子树的左右侧，要么是待删除结点右子树的最左侧，因此一定是符合上述三种情况中的某一种，此时删除这个结点，按上述三种情况进行相应处理即可。

上述四种情况，涵盖了二叉搜索树中所有可能出现的删除情况，按照这样逻辑写出的代码，对于普通结点，基本能够通用，但对于整棵树的根结点，由于根结点的特殊性，可能会有谬误，因此对于无法兼容根结点的地方，需要对根结点进行特殊处理。

bool erase(const T& key)
{//删除的情况，相对而言，是比较复杂的//先找到删除位置，再删除Node* cur = _root;Node* pre = nullptr;while (cur){if (key < cur->_key){pre = cur;cur = cur->_left;}else if (key > cur->_key){pre = cur;cur = cur->_right;}elsebreak;}if (cur == nullptr)return false;else{//被删除结点的左结点为空if (cur->_left == nullptr){if (pre == nullptr)_root = cur->_right;//对根结点的特殊处理else if (pre->_left == cur)pre->_left = cur->_right;elsepre->_right = cur->_right;delete cur;}//被删除结点的右结点为空，左结点不为空else if (cur->_right == nullptr){if (pre == nullptr)_root = cur->_left;//对根结点的特殊处理else if (pre->_left == cur)pre->_left = cur->_left;elsepre->_right = cur->_left;delete cur;}//被删除结点的左右结点均不为空else{//找被删除结点的左子树的最大结点或右子树的最小结点//找左子树的最大结点，即最右结点Node* replace = cur->_left;Node* pre_replace = cur;while (replace->_right){pre_replace = replace;replace = replace->_right;}swap(cur->_key, replace->_key);if (pre_replace->_left == replace)pre_replace->_left = replace->_left;elsepre_replace->_right = replace->_left;delete replace;}}return true;
}

2.5 销毁

二叉搜索树的销毁，也就是二叉树的销毁，使用二叉树的后序遍历进行销毁。

~BSTree()
{Destroy(_root);_root = nullptr;
}void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}