二叉搜索树简介
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
1. 二叉搜索树的查找
- a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- b、最多查找高度次，走到到空，还没找到，这个值不存在。
2. 二叉搜索树的插入
插入的具体过程如下：
- a. 树为空，则直接新增节点，赋值给root指针
- b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
3. 二叉搜索树删除
- 删除结点的左子树为空或者删除结点的右子树为空
解决方法：将它的不为空的子树给它的父亲结点
- 删除结点的左子树和右子树都不为空
替换法：找左子树的最右结点或找右子树的最左结点，先交换，再删除这个结点
应用场景
Key的搜索模型：确定一个值在不在？例如门禁系统
Key/ Value 模型：确定Key在不在，并通过Key查找 value
例如字典，通过汉语查找英语，统计某单词出现的次数
代码实现
注意：代码使用了迭代和循环两种方式来实现二叉搜索树
在循环法来对搜索二叉树进行操作时，需要用一个指针来记录它的父亲，而使用递归法来对搜索二叉树进行操作时，不需要用指针来记录，只需要传参的时候传引用即可，就能直接对指向进行修改！
#pragma once #include<iostream> using namespace std; template <class K> struct BinarySearchTree { BinarySearchTree(const K& x = K()) :_left(nullptr) , _val(x) , _right(nullptr) {} K _val; BinarySearchTree<K>* _left; BinarySearchTree<K>* _right; }; template <class K> class BSTree { typedef BinarySearchTree<K> BST; public: BSTree() {} // 循环插入 bool Insert(const K& x) { if (_root == nullptr) { _root = new BinarySearchTree<K>(x); } else { BST* cur = _root; BST* parent = nullptr; while (cur) { if (cur->_val < x) { parent = cur; cur = cur->_right; } else if (cur->_val > x) { parent = cur; cur = cur->_left; } else { return false;//排序二叉树中不能插入相同的数 } } cur = new BinarySearchTree<K>(x); if (x > parent->_val) { parent->_right = cur; } else { parent->_left = cur; } } return true; } //循环查找 bool* find(const K& x) { if (_root == nullptr) { return false; } BST* cur = _root; while (cur) { if (cur->_val < x) { cur = cur->_right; } else if (cur->_val > x) { cur = cur->_left; } else { return true; } } return false; } // 循环删除 bool erase(const K& x) { if (_root == nullptr) { return false; } else { BST* cur = _root; BST* parent = cur; while (cur) { if (cur->_val < x) { parent = cur; cur = cur->_right; } else if (cur->_val > x) { parent = cur; cur = cur->_left; } else { // 找到即将要删除的结点了 //左孩子为空或者右孩子为空的情况 if (cur->_left == nullptr||cur->_right == nullptr) { if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (parent->_val < x) { parent->_right = cur->_right; } else parent->_left = cur->_right; } } else { if (cur == _root) { _root = cur->_left; } else { if (parent->_val < x) { parent->_right = cur->_left; } else parent->_left = cur->_left; } } delete cur; cur = nullptr; return true; } // 左右孩子都存在的情况 // 替换法 else { // cur 为要删除的结点，且左右子树都不为空 BST* del = cur->_left; BST* parent = del; while (del->_right) { parent = del; del = del->_right; } swap(cur->_val, del->_val); parent->_right = del->_left; delete del; del = nullptr; return true; } } } return false; } } // 前序遍历时，恰好为升序 void Preorder() { _Preorder(_root); cout << endl; } // 递归插入 bool insertR(const K& x) { if (_root == nullptr) { _root = new BinarySearchTree<K>(x); return true; } else { return _insertR(_root, x); } } // 递归查找 bool findR(const K& x) { return _findR(_root, x); } //递归删除 bool eraseR(const K& x) { return _eraseR(_root, x); } private: void _Preorder(BST* root) { if (root == nullptr) { return; } _Preorder(root->_left); cout << root->_val << " "; _Preorder(root->_right); } bool _eraseR(BST*& root, const K& x) { if (root == nullptr) return false; if (root->_val < x) return _eraseR(root->_right, x); else if (root->_val > x) return _eraseR(root->_left, x); else { if (root->_left==__nullptr || root->_right==nullptr) { if (root->_left == nullptr) { BST* del = root; root = root->_right; delete del; return true; } else { BST* del = root; root = root->_left; delete del; return true; } } else { BST*& cur = root->_right; while (cur->_left) { cur = cur->_left; } swap(cur->_val, root->_val); return _eraseR(root->_right, x); } } } bool _findR(BST*root, const K& x) { if (root == nullptr) return false; if (root->_val < x) return _findR(root->_right, x); else if (root->val > x) return _findR(root->_left, x); else return true; } bool _insertR(BST*& root, const K& x) { if (root == nullptr) { root = new BinarySearchTree<K>(x); return true; } if (root->_val < x) { return _insertR(root->_right, x); } else if (root->_val > x) { return _insertR(root->_left, x); } else return false; } BST*_root = nullptr; };
