【数据结构进阶】二叉搜索树_set,c++

🔥个人主页： Forcible Bug Maker
🔥专栏： C++ || 数据结构

目录

• 🌈前言
• 🔥二叉搜索树
• 🔥 二叉搜索树的实现
• • ==Insert（插入）==
  • ==find（查找）==
  • ==erase(删除)==
  • ==destroy（析构）==
  • ==InOrder（中序遍历）==
  • ==拷贝构造==
• 🔥二叉搜索树的应用
• 🔥二叉搜索树的性能
• 🌈结语

🌈前言

本篇博客主要内容：二叉搜索树的介绍及自实现。

基础的二叉树在前面的C数据结构阶段已经讲过（初阶数据结构之—二叉树链式结构）。之前因为用C语言的话，实现更高级数据结构比较困难，所以并没有往后展开。到了现在，已经有了一定的C++功底，就可以开启我们数据结构进阶部分的内容了。对于二叉搜索树的特性了解，有助于后续更好的理解map和set的特性。本节课作为学习更高阶数据结构的基础，对后续学习来说至关重要。

🔥二叉搜索树

二叉搜索树的概念：
二叉搜索树又称二叉排序树，它或者是一颗空树，或者具有以下三种性质：

• 若它的左子树不为空，则左子树上的所有结点都小于根节点的值
• 若它的右子树不为空，则右子树上的所有结点都大于根节点的值
• 它的左右子树也分别为二叉搜索树

二叉搜索树的中序遍历是有序的。

🔥 二叉搜索树的实现

以下是需要实现的二叉搜索树的头文件内容

#pragma once#includenamespace ForcibleBugMaker{ template<class K>struct BSTreeNode{ BSTreeNode<K>(const K& k = K()):_key(k), _left(nullptr), _right(nullptr){ }K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;};template<class K>class BSTree{ typedef BSTreeNode<K> Node;public:BSTree() = default;BSTree(const BSTree<K>& t);bool Insert(const K& key);Node* Find(const K& key);bool Erase(const K& key);~BSTree();void InOrder();private:Node* _root = nullptr;};}

二叉搜索树的结点中有三个成员变量，分别是
_key：存储数据；_left：指向左子树；_right：指向右子树。将其在BSTree中typedef成Node方便后续使用。

Insert（插入）

二叉树的插入，主要考虑两种情况：

1. 树为空，则直接新增结点，赋给root指针。
2. 树不为空，按二叉搜索树性质查找插入位置，插入新结点，如key结点值存在，则插入失败。
   

bool Insert(const K& key){ if (_root == nullptr) { _root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){ if (cur->_key < key) { parent = cur;cur = cur->_right;}else if (cur->_key > key) { parent = cur;cur = cur->_left;}else return false;}if (parent->_key < key) parent->_right = new Node(key);else parent->_left = new Node(key);return