【C++课程学习】：二叉搜索树

🎁个人主页：我们的五年

🔍系列专栏：C++课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

二叉树搜索树的概念：

节点的结构：

⚽️结构：

⚽️ 构造函数：

搜索二叉树的查找：

⛳️查找步骤：

⛳️时间复杂度：

⛳️代码实现：

搜索二叉树的插入：

🌴插入步骤：

🌴插入代码：

二叉树的删除：

🍁删除步骤：

●叶子节点（左右指针都为空）：

●只有一个孩子（左子树为空，或者右子树为空）：

●有两个孩子：

🍁实现代码：

拷贝构造，析构函数：

搜索二叉树的应用：

二叉树搜索树的概念：

二叉搜索树也叫二叉排序树，二叉查找树。

二叉搜索树可以为空，但是不为空的时候，具有下面的性质：

●非空左子树的所有键值小于根的键值。

●非空右子树的所有键值大于根的键值。

●左右子树任然是搜索二叉树。

节点的结构：

⚽️结构：

因为搜索二叉树也是二叉树，要定义左右两个节点指针。此时先以K树讲解。此时的节点结构为：

⚽️ 构造函数：

在实践情况中，我们一般用一个T类型的值（键值）去进行构造一个节点。其他的用BST_node去进行拷贝构造基本是不可能的。所以写这一个构造函数就够了。

struct BST_Node {//用key值进行构造BST_Node(const T& key=T()):_left(nullptr),_right(nullptr),_key(key){}//左右节点指针，以及键值BST_Node<T>* _left;BST_Node<T>* _right;T _key;
};

另外下面还有对该节点和节点指针重命名的。

typedef BST_Node<T> node;
typedef node* pnode;

搜索二叉树的查找：

⛳️查找步骤：

如果要查找一个值，根据二插树的性质。从根节点开始，如果根的键值不是，那么如果要查找的键值大于根，就往右子树走。如果小于根的键值，那么就往左子树走。如果走到空了，还没找到，那么这个值就不存在。

⛳️时间复杂度：

最坏情况是查找树的高度次。

但是此时不是满二叉树，不能认为现在的二叉树的高度为（logN）+1。

最坏二叉树的高度为N，所以查找就是N次。时间复杂度就是O（N）。

⛳️代码实现：

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

搜索二叉树的插入：

🌴插入步骤：

根据搜索二叉树的规则，如果要插入的值小于此时的键值，那么就往左边走，如果大于此时的键值就往右走。直到走到空为止，然后用一个键值为key的新节点插入到搜索二叉树中。要插入，就要知道父节点，所以在走的过程中，要用parent_cur时刻记录cur的父节点。

因为当_root为空时进行了特判，所以parent_cur不可能为nullptr,所以不会发生对野指针的解引用。

🌴插入代码：

	bool insert(const T& key){//当根节点为nullptr时，直接向_root插入节点if (_root == nullptr){_root = new node(key);return true;}//_root为二叉搜索树的根节点pnode cur = _root;pnode parent_cur = nullptr;while (cur){//如果要插入的值小于此时的根节点，就往左边走if (key < cur->_key){parent_cur = cur;cur = cur->_left;}//如果要插入的值大于此时的根节点，就往右边走else if (key > cur->_key){parent_cur = cur;cur = cur->_right;}//此时表示二叉树中存在该值，就返回falseelsereturn false;}//申请节点，cur在parent_cur的左边就把新节点插入parent_cur的左边，如果不是就插入右边pnode newnode = new node(key);if (key< parent_cur->_key)parent_cur->_left = newnode;elseparent_cur->_right = newnode;return true;}

二叉树的删除：

🍁删除步骤：

把搜索二叉树的节点进行分类，具体点可以分为三种情况：

●叶子节点（左右指针都为空）：

删除叶子节点时，直接删除即可，如果叶子节点在父节点的左边，就把父节点的左指针变为空，如果叶子节点在父节点的右边，就把父节点的右指针变为nullptr。

注意：如果此时叶子节点为_root（根节点），就没有父节点，只需把_root变为nullptr。

●只有一个孩子（左子树为空，或者右子树为空）：

要删除这样的节点也是比较简单的，只需要把该节点的孩子给父节点就可以。叶子节点也可以当成这种情况进行处理。

同样也应该注意该节点是不是根（_root）节点。

●有两个孩子：

这种情况，就不能直接把两个孩子都给父亲，因为一个节点最多有两个孩子，如果父节点已经有一个孩子了，就不能把要删除的节点两个孩子给父节点了。

所以我们就需要去找一个节点来带这两个孩子。要找的这个节点要有这样的性质：

●如果删除的节点在父节点左边，那么找到的新节点就要比父节点小。相反就比父节点大。

解决办法：

就在要删除的这棵树中找，就满足这样的性质。

下面图中在绿色这棵树中找，全部满足键值大于根节点5。

●新的节点必须比左树所有节点都大，比右树都小。

解决办法：

1.左树的节点都比根的键值小，那就比所有右树节点小。左树所有节点都满足了比右树都小。

2.在左树中找到最大就满足了左树节点都小于这个节点。从左树开始，一直往右边走，就可以满足这三个性质。

上图的键值为7的节点。

🍁实现代码：

	bool erase(const T& key){pnode parent_cur = nullptr;pnode cur = _root;//寻找键值为key的节点while (cur){if (key < cur->_key){parent_cur = cur;cur = cur->_left;}else if (key > cur->_key){parent_cur = cur;cur = cur->_right;}elsebreak;	//找到了}if(cur==nullptr)return false;//只有右孩子，叶子节点可以当成这种情况处理if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent_cur->_left == cur)parent_cur->_left = cur->_right;elseparent_cur->_right = cur->_right;}delete cur;return true;}//只有左孩子else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent_cur->_left == cur)parent_cur->_left = cur->_left;elseparent_cur->_right = cur->_left;}delete cur;return true;}//有两个孩子else{pnode left_max_parent = cur;pnode left_max = cur->_right;while (left_max->_right){left_max_parent = left_max;left_max = left_max->_right;}cur->_key = left_max->_key;if (left_max == left_max_parent->_left)left_max_parent->_left=left_max->_left;elseleft_max_parent->_right=left_max->_left;delete left_max;return true;}}

拷贝构造，析构函数：

进行深拷贝，从_root开始遍历，进行深拷贝。

析构函数也要进行逐一释放。

	BST(const BST<T>& t){_root = copy(t._root);}pnode copy(pnode root){if (root == nullptr)return root;pnode newnode = new node;newnode->_key = root->_key;newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;}~BST(){Destroy(_root);}void Destroy(pnode root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}

搜索二叉树的应用：

K模型：

上面所说的是K模型，在插入一些数以后，可以去查找某个值在不在这棵树中。例如：查找一个单词是否正确，就可以去一棵有所以单词的搜索二叉树中寻找在不在树中。

KV模型：

就是一个Key值，会与一个value值对应，找到了key值，就可以得到value值。

例如：英汉字典，每个单词就可以对应一个中文意思，找到了key（英文）就可以得到value（中文）。

这种二叉树有极端情况：

使得它的时间复杂度为O（N）。