4、二叉搜索树的插入
- 具体操作过程：
- 若key大于当前结点的数据域之值，则插入右子树
- 若key小于当前结点的数据域之值，则插入左子树
- 若key等于当前结点的数据域之值，则插入失败，返回false
- 若走到空结点直接插入，插入成功，返回true
- 示图：插入56
- 迭代实现：
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* prev = nullptr; while (cur) { if (cur->_key > key) { prev = cur; cur = cur->_left; } else if (cur->_key < key) { prev = cur; cur = cur->_right; } else { return false; } } cur = new Node(key); //依靠键值比较来决定连接位置（依靠节点地址来判断会误判） if (prev->_key > key) { prev->_left = cur; } else { prev->_right = cur; } return true; }
- 递归实现：
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->_left, key); } else if (root->_key < key) { return _InsertR(root->_right, key); } else { return false; } }
5、二叉搜索树的删除
- 具体操作过程：
若查找元素不存在在二叉搜索树中，则返回false
若查找元素存在，则可能分为下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
注：实际情况a可以与情况b或者c合并起来
最终的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
示图：删除91
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
示图：删除29
情况d：替换删除，在左子树中找到key最大的（或则在右子树中找到key最小的），与当前结点交换key，然后删除左子树中key最大结点（或则在右子树key最小的结点）
示图：删除20
迭代实现：
bool Erase(const K& key) { Node* cur = _root; Node* prev = nullptr;//记录父结点 while (cur) { if (cur->_key > key) { prev = cur; cur = cur->_left; } else if (cur->_key < key) { prev = cur; cur = cur->_right; } else//找到了 { //分情况讨论 if (cur->_left == nullptr) { //根节点特殊处理 if (cur == _root) { _root = cur->_right; } else { //判断是左还是右 if (prev->_left == cur) { prev->_left = cur->_right; } else { prev->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (prev->_left == cur) { prev->_left = cur->_left; } else { prev->_right = cur->_left; } } delete cur; } else { //找到左子树中最大的结点 Node* maxLeft = cur->_left; while (maxLeft->_right) { maxLeft = maxLeft->_right; } K max = maxLeft->_key; //先删再替换 Erase(max); cur->_key = max; } return true; } } return false; }
- 递归实现：
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->_left, key); else if (root->_key < key) return _EraseR(root->_right, key); else { //记录当前结点 Node* del = root; if (root->_left == nullptr) { root = root->_right; } else if (root->_right == nullptr) { root = root->_left; } else { //找到右边最小结点 Node* minR = root->_right; while (minR->_left) { minR = minR->_left; } //替换值 root->_key = minR->_key; _EraseR(root->_right, root->_key); return true; } delete del; return true; } }
三、二叉搜索树的应用
- K模型：
概念：
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值
示例：给一个单词word，判断该单词是否拼写正确
以单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中,检索该单词是否存在，存在则拼写正确，不存在则拼写错误
KV模型：
概念：
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值
示例：
英汉词典：通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对
统计单词次数：统计后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对
实现一个简单的英汉词典dict：
<单词，中文含义>为键值对构造二叉搜索树,二叉搜索树需要比较，键值对比较时只比较Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的key
KV模型：
template<class K, class V> struct BSTNode { BSTNode(const K& key = K(), const V& value = V()) : _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value) {} BSTNode<T>* _pLeft; BSTNode<T>* _pRight; K _key; V _value }; template<class K, class V> class BSTree { typedef BSTNode<K, V> Node; typedef Node* PNode; public: BSTree() : _pRoot(nullptr) {} ~BSTree(); PNode Find(const K& key); bool Insert(const K& key, const V& value) { // ... PNode pCur = _pRoot; PNode pParent = nullptr; while (pCur) { pParent = pCur; if (key < pCur->_key) pCur = pCur->_pLeft; else if (key > pCur->_key) pCur = pCur->_pRight; // 元素已经在树中存在 else return false; } // ... return true; } bool Erase(const K& key) { // ... return true; } private: PNode _pRoot; };
