什么是二叉搜索树
二叉搜索树是普通二叉树的升级，普通二叉树除了存储数据以外好像没有别的优势了，但是二叉搜索树不同，如果对搜索树采用中序遍历得到的结果是一串有序的数字。
二叉搜索树又称为二叉排序树，它要么是一棵空树，要么是一棵具有以下特点的树：
1.如果它的左子树不为空，那么它左子树上所有节点的值都小于根节点的值
2.如果它的右子树不为空，那么它右子树上所有节点的值都小于根节点的值
3.它的左右子树也是一棵二叉搜索树
它的结构如下：
template<class K> struct BSTreeNode { //树的节点包含它的左子树和右子树指针以及这个节点中的值 BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; //来个构造函数高一下子 BSTreeNode(int key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; class BSTree { public: typedef BSTreeNode<K> Node; private: Node*_root； };
二叉搜索树的中序遍历
因为中序遍历得到的结果是一串有序的数字列，所以对于二叉搜索树而言中序遍历才是王道。但是因为中序遍历要从根节点开始，也就说要给函数传根节点，但是根节点作为成员变量是私有的，所以这里采用了嵌套的方式(将真正的中序遍历函数私有化，放出一个公有的调用接口）：
void Inorder() { //中序遍历 _Inorder(_root); cout << endl; } private: //因为中序遍历需要根作为参数，为了保持封装，在这里嵌套一下 void _Inorder(Node *root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_key << " "; _Inorder(root->_right); }
二叉搜索树的查找
在一棵二叉搜索树中搜索一个元素，最坏的结果也就是O(N)，但如果这个搜索树一个接近完全二叉树的情况，则只需要查找高度次。
如果是一棵接近完全二叉，查找复杂度为O(logN)，目前我学过的查找中只有二分能达到这样的效率，但是二分有诸多限制，反而不如搜索二叉树来的强大。
所以后面还有平衡二叉树等对结果做进一步的限制，能大大的提升查找的效率
查找的非递归写法
在搜索树中查找某一个值，如果这个值比根节点的值要小，就往根的左子树中找；如果比根节点的值要大，就往右子树中找。
bool Find(const K& key) { if (_root == nullptr) return false; else { Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else { return true; } } } return false; }
查找的递归写法
//为了不破坏封装，这个函数要被设置成私有的 Node* _FindR(Node* root, const K& val) { //递归式查找 if (root == nullptr) return nullptr; if (root->_key > val) { return _FindR(root->_left, val); } else if (root->_key < val) { return _FindR(root->_right, val); } return root; } //这个是暴露在外面的公有接口 bool FindR(const K& val) { return _FindR(_root, val) == nullptr ? false : true; }
二叉搜索树的插入
向搜索树中插入不能破坏搜索树的结构，所以不能插入和树种元素相同的值
非递归
//二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构 //它左孩子的值比根小，右孩子比根大 bool Insert(const K& key) { //插入，分为空树插入和非空树插入 if (_root == nullptr) { _root = new Node(key); return true; } else { //如果要插入的这个值比当前值要大就往右边走，否则就往左边走 Node* cur = _root; Node* parent = cur; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { return false;//不允许插入相同的值 } } //找到要插入的位置了，将值插入进去 cur = new Node(key); //还要判断一下把这个节点链接在parent的左边还是右边 if (parent->_key > key) parent->_left = cur; else if (parent->_key < key) parent->_right = cur; } return true; }
1.如果是向空树中插入，就直接new一个新节点作为根节点
2.如果是向非空树种插入，首先要找到插入位置，如果在寻找位置的时候发现相同值，直接返回false
3.找到合适位置以后，要将该节点与树链接起来，所以要提前准备一个父节点指针标记插入位置的父节点
递归
递归写法的唯一难处就是在于任何标记插入位置的父节点，这里我们可以采用引用的方式，这个引用用到这里真是妙绝
//递归插入的公共接口 bool InsertR(const K&val) { return _InsertR(_root, val); } //递归插入的私有函数 bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼 { if (root == nullptr) { //空就直接插入 root = new Node(val); return true; } Node* cur = root; while (cur) { if (cur->_key > val) return _InsertR(cur->_left, val); else if (cur->_key < val) return _InsertR(cur->_right, val); else return false;//不允许相同的元素插入 } }
这里为什么给一个引用就能直接链接上呢？主要还是因为这一层的
root是上一层root->left或者root->right的别名
二叉搜索树的删除
删除操作是二叉搜索树种最难的一个，因为它涉及到的情况相对比较多
1.如果这个要被删除的节点有一个子树是空树，那么只要将不为空的子树交给被删除节点的父节点即可（这种方法又叫托孤），当然也不能排除这个要被删除的节点是根节点
2.如果这个被删除的节点的左右子树都不为空，那么就不能直接删除，我采用的是替换法删除，找该节点左子树中的最大值或者右子树的最小值作为替换值，然后将替换值的那个节点删除
非递归
bool Erase(const K& val) { //要删除这个节点，首先要找到这个节点 Node* cur = _root; Node* parent =cur; while (cur) { if (cur->_key > val) { parent = cur; cur = cur->_left; } else if (cur->_key < val) { parent = cur; cur = cur->_right; } else { //这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除 //有一个节点为空，判断是这个节点的哪个节点是空 if (cur->_left == nullptr) { //不排除cur是根节点 if (cur == _root) { _root = cur->_right; } else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子 { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur;//要把节点释放掉 } else { //这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换 Node* minRight = cur->_right; while (minRight->_left) { parent = minRight; minRight = minRight->_left; } //将值替换 cur->_key = minRight->_key; //最左节点可能有右孩子，所以不能直接将最左节点删除 if (parent->_left == minRight) parent->_left = minRight->_right; else parent->_right = minRight->_right; delete minRight; } return true; } } return false; }
递归
//递归删除的公共接口 bool EraseR(const K& val) { return _EraseR(_root, val); } bool _EraseR(Node*& root, const K& val) { if (root == nullptr) return false; Node* cur = root; Node* parent = cur; if (cur->_key > val) return _EraseR(root->_left, val); else if (cur->_key < val) return _EraseR(root->_right, val); else { //找到节点，删除 Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点 if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { Node* rightMin = root->_right; while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点 { rightMin = rightMin->_left; } root->_key = rightMin->_key;//找到了交换key //对子树进行递归删除 return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归 } delete del; return true; } }
二叉搜索树的使用场景
k模型
k模型就是以key作为关键码，结构中只需要存储key值即可。key模型的应用场景有很多，比如查找一本书中的错别字（将词库导入树种，再将书种的每个词去树中搜索一遍，找不到是错别字），比如鉴定一个车牌是否是该停车场的用户（只要将登记的车牌导入搜索树中，当有车来的时候将该车的车牌作为key值去树中检索以下即可）等。二叉搜索树就是一种key模型。
#pragma once #include<iostream> using namespace std; //写一个二叉搜索树 namespace wbm { template<class K> struct BSTreeNode { //树的节点包含它的左子树和右子树指针以及这个节点中的值 BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; //来个构造函数高一下子 BSTreeNode(int key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; //有了单个节点，再来搞一下子结构 template<class K> class BSTree { typedef BSTreeNode<K> Node; public: ~BSTree() { //循环遍历释放节点，因为要传根节点，这里也考虑使用嵌套 Destory(_root); _root = nullptr; } //二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构 //它左孩子的值比根小，右孩子比根大 bool Insert(const K& key) { //插入，分为空树插入和非空树插入 if (_root == nullptr) { _root = new Node(key); return true; } else { //如果要插入的这个值比当前值要大就往右边走，否则就往左边走 Node* cur = _root; Node* parent = cur; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { return false;//不允许插入相同的值 } } //找到要插入的位置了，将值插入进去 cur = new Node(key); //还要判断一下把这个节点链接在parent的左边还是右边 if (parent->_key > key) parent->_left = cur; else if (parent->_key < key) parent->_right = cur; } return true; } //递归插入 bool InsertR(const K&val) { return _InsertR(_root, val); } //查找,找到返回节点，找不到返回空 bool Find(const K& key) { if (_root == nullptr) return false; else { Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else { return true; } } } return false; } bool FindR(const K& val) { return _FindR(_root, val) == nullptr ? false : true; } bool Erase(const K& val) { //要删除这个节点，首先要找到这个节点 Node* cur = _root; Node* parent =cur; while (cur) { if (cur->_key > val) { parent = cur; cur = cur->_left; } else if (cur->_key < val) { parent = cur; cur = cur->_right; } else { //这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除 //有一个节点为空，判断是这个节点的哪个节点是空 if (cur->_left == nullptr) { //不排除cur是根节点 if (cur == _root) { _root = cur->_right; } else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子 { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur;//要把节点释放掉 } else { //这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换 Node* minRight = cur->_right; while (minRight->_left) { parent = minRight; minRight = minRight->_left; } //将值替换 cur->_key = minRight->_key; //最左节点可能有右孩子，所以不能直接将最左节点删除 if (parent->_left == minRight) parent->_left = minRight->_right; else parent->_right = minRight->_right; delete minRight; } return true; } } return false; } //删除的递归 bool EraseR(const K& val) { return _EraseR(_root, val); } void Inorder() { //中序遍历 _Inorder(_root); cout << endl; } private: //因为中序遍历需要根作为参数，为了保持封装，在这里嵌套一下 void _Inorder(Node *root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_key << " "; _Inorder(root->_right); } Node* _FindR(Node* root, const K& val) { //递归式查找 if (root == nullptr) return nullptr; if (root->_key > val) { return _FindR(root->_left, val); } else if (root->_key < val) { return _FindR(root->_right, val); } return root; } bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼 { if (root == nullptr) { //空就直接插入 root = new Node(val); return true; } Node* cur = root; while (cur) { if (cur->_key > val) return _InsertR(cur->_left, val); else if (cur->_key < val) return _InsertR(cur->_right, val); else return false;//不允许相同的元素插入 } } bool _EraseR(Node*& root, const K& val) { if (root == nullptr) return false; Node* cur = root; Node* parent = cur; if (cur->_key > val) return _EraseR(root->_left, val); else if (cur->_key < val) return _EraseR(root->_right, val); else { //找到节点，删除 Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点 if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else { Node* rightMin = root->_right; while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点 { rightMin = rightMin->_left; } root->_key = rightMin->_key;//找到了交换key //对子树进行递归删除 return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归 } delete del; return true; } } void Destory(Node* root) { if (root == nullptr) return; Destory(root->_left); Destory(root->_right); delete root; } private: Node* _root=nullptr; //不写构造，直接给缺省值 }; }
