引言
二叉树在之前的数据结构章节讲解过，当时使用C来实现。而如今学习的二叉搜索树，便是二叉树的进阶，也更适合使用C++来实现。
一、二叉搜索树介绍
二叉搜索树（BST，Binary Search Tree），又称为二叉排序树。
它满足以下性质：
- 非空左子树的所有键值小于其根结点的键值
- 非空右子树的所有键值大于其根结点的键值
- 左右子树均为二叉搜索树
二、二叉搜索树的模拟实现
2.1 结点
template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) : _left(nullptr) , _right(nullptr) , _key(key) {} };
细节：在二叉搜索树中，一般更喜欢用K作为模板参数，用key作为数据，称为键值。
2.2 成员变量
template<class K> class BSTree { typedef BSTreeNode<K> Node; protected: Node* _root = nullptr; };
2.3 默认成员函数
2.3.1 constructor
//写法一 BSTree() : _root(nullptr) {} //写法二 BSTree() = default;//强制生产默认构造
2.3.2 copy constructor
BSTree(const BSTree<K>& t) { _root = Copy(t._root); } Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; }
细节：写一个子函数Copy，进行前序遍历递归拷贝
2.3.3 operator=
BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; }
细节：现代写法，直接拷贝完交换
2.3.4 destructor
~BSTree() { Destroy(_root); } void Destroy(Node*& root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; root = nullptr; }
细节：
- 写一个子函数Destroy，进行后序遍历递归释放
- 参数为Node*&，这样就可以在函数内置空根节点
2.4 中序遍历
为什么只介绍中序遍历呢？二叉搜索树，之所以又称为二叉排序树，是因为在中序遍历时，便能将数据按升序遍历。
void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
细节：同样，一般要递归写一个子函数，再进行传参控制
2.5 查找
二叉搜索树，其最大优势肯定是在于搜索！
2.5.1 迭代实现
bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; }
细节：
- 查找的key比当前结点的_key大，则往右查找
- 查找的key比当前结点的_key小，则往左查找
- 找到返回true，走到空找不到返回false
2.5.2 递归实现
bool FindR(const K& key) { return _FindR(_root, key); } bool _FindR(Node* root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else { return true; } }
2.6 插入
2.6.1 迭代实现
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; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
细节：
- 若根为空，直接创建结点，返回true
- 设置parent变量，记录父节点，以便在cur走到空时进行插入
- 插入前，要判断用左指针还是右指针链接
2.6.2 递归实现
bool InsertR(const K& key) { return _InsertR(_root, key); } bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if (root->_key > key) { return _InsertR(root->_left, key); } else { return false; } }
细节：参数为Node*&，使得当前root为空，却可以直接创建节点链接（因为此时root是其父节点左右指针的引用）
2.7 删除
2.7.1 迭代实现
bool Erase(const K& key) { 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 { if (cur->_right == nullptr)//右子树为空 { if (cur == _root) { _root = _root->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; } else if (cur->_left == nullptr)//左子树为空 { if (cur == _root) { _root = _root->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } else//左右子树均不为空 { //这里选择找右子树的最左节点 Node* pminRight = cur; Node* minRight = cur->_right; while (minRight->_left) { pminRight = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; if (pminRight->_right == minRight) { pminRight->_right = minRight->_right; } else { pminRight->_left = minRight->_right; } delete minRight; } return true; } } return false; }
细节：
- 首先依然要parent记录父节点，进行查找
- 找到了，分三种删除情况：
- 右子树为空
- 左子树为空
- 左右子树均不为空
- 左右子树一边为空时，先判断parent是否为空，如果为空，代表cur为_root，需要移动_root；如果不为空，则再判断左右指针链接
- 左右子树均不为空时，寻找右子树的最左结点minRight（也可以是左子树的最右结点）来替代cur，注意minRight可能有孩子，还要设置pminRight记录其父节点位置，判断左右指针链接
2.7.2 递归实现
bool EraseR(const K& key) { return _EraseR(_root, key); } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr)//右子树为空 { root = root->_left; } else if (root->_left == nullptr)//左子树为空 { root = root->_right; } else { Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); return _EraseR(root->_right, key); } delete del; return true; } }
细节：
- 参数为Node*&，使得左右子树一边为空时，不用判断，直接链接（将两种情况一并处理了）
- 左右子树均不为空时，交换待删除root和minRight的键值key，再递归其右子树删除
三、二叉搜索树的应用
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
- 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
四、二叉树进阶面试题
一、根据二叉树创建字符串
二、二叉树的层序遍历
三、二叉树的最近公共祖先
四、二叉搜索树转换双向链表
五、构造二叉树
5.1 前序与中序
5.2 中序与后序
六、二叉树的前中后序遍历（非递归）
6.1 前序
6.2 中序
6.3 后序
真诚点赞，手有余香
