3.2.6 ~BinarySearchTree（析构）
private: //析构子函数 void Destruction(BSTNode*& root) { if (root == nullptr) { return; } //先去释放左孩子和右孩子的空间资源 Destruction(root->_left); Destruction(root->_right); //再去释放root自己的空间资源 delete root; root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝 return; } public: //析构函数 ~BinarySearckTree() { Destruction(_root); }
3.2.7 BinarySearchTree(const Self& tree)（拷贝构造）
注意拷贝构造不能直接去调用 insert，因为数据插入的顺序不同，这棵树最终的结构也是不同的，虽然最终也符合二叉树的结构，但是还是和被拷贝的树有所不同。正确做法是，走一个前序遍历，遍历到 tree 的一个结点时，去 new 一个结点，存储同样的值。
写法一：
//拷贝构造函数的子函数 private: void Construct(BSTNode*& root, BSTNode* copy) { if (copy == nullptr) { root = nullptr; return; } root = new BSTNode(copy->_val);//通过引用直接来实现链接关系 Construct(root->_left, copy->_left); Construct(root->_right, copy->_right); } public: //拷贝构造 BinarySearchTree(const Self& tree) :_root(nullptr) { Construct(_root, tree._root); }
写法二：
private: //拷贝构造子函数(写法二) BSTNode* Construct(BSTNode* root) { if (root == nullptr) { return nullptr; } BSTNode* newnode = new BSTNode(root->_val); newnode->_left = Construct(root->_left);//通过返回值来实现链接关系 newnode->_right = Construct(root->_right); return newnode; } public: //拷贝构造(写法二) BinarySearchTree(const Self& tree) { _root = Construct(tree._root); }
小Tips：上面两种写法的不同点在于，方法一是通过引用去实现链接关系，方法二则是通过返回值的方式来实现链接关系。
3.2.8 operator=（赋值运算符重载）
public: //赋值运算符重载(现代写法) Self& operator=(Self tree) { swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点 return *this; }
四、二叉搜索树的应用
4.1 K模型
K模型即只有一个 Key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。比如：给一个单词 word，判断该单词是否拼写正确，具体方式如下：
- 以词库中所有单词集合中的每个单词作为 Key，构建一颗二叉搜索树。
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
我们上面手搓的这可二叉搜索树就是 Key 模型，因为这颗树的结点里面只能存储一个值，这个值就是 Key。
4.2 KV模型
KV 模型即每一个关键码 Key，都有与之对应的的值 Value，即 <Key，Value> 的键值对。这种方式在现实生活中十分常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word，Chinese> 就构成一种键值对。
- 再比如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现次数就是 <word，count> 就构成一种键值对。
4.2.1 KV 模型手撕
#pragma once namespace K_V { template <class K, class V> struct BinarySearchTreeNode { typedef BinarySearchTreeNode<K, V> TNode; BinarySearchTreeNode(const K& key = K(), const V& val = V()) :_key(key) , _val(val) , _left(nullptr) , _right(nullptr) {} K _key; V _val; TNode* _left; TNode* _right; }; template <class K, class V> class BinarySearchTree { typedef BinarySearchTreeNode<K, V> BSTNode; typedef BinarySearchTree<K, V> Self; private: void _InOrder(BSTNode* root) const { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << "--" << root->_val << endl; _InOrder(root->_right); } BSTNode* _FindR(BSTNode* root, const K& key)//KV模型中的Key不能被修改，但是Val可以被修改 { if (root == nullptr) { return nullptr; } if (key < root->_key) { return _FindR(root->_left, key); } else if (key > root->_key) { return _FindR(root->_right, key); } else { return root; } } //插入(递归---版本一) //bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key) //{ // if (root == nullptr)//为空说明就是在该位置插入 // { // BSTNode* newnode = new BSTNode(key); // if (parent != nullptr) // { // if (key < parent->_key) // { // parent->_left = newnode; // } // else // { // parent->_right = newnode; // } // } // else // { // root = newnode; // } // return true; // } // //root不为空说明还没有找到待插入的位置，还得继续找 // if (key < root->_key) // { // return _InsertR(root->_left, root, key); // } // else if (key > root->_key) // { // return _InsertR(root->_right, root, key); // } // else // { // return false; // } //} //插入(递归---版本二) bool _InsertR(BSTNode*& root, const K& key, const V& val) { if (root == nullptr)//为空说明就是在该位置插入 { root = new BSTNode(key, val); return true; } //root不为空说明还没有找到待插入的位置，还得继续找 if (key < root->_key) { return _InsertR(root->_left, key, val); } else if (key > root->_key) { return _InsertR(root->_right, key, val); } else { return false; } } //删除递归版 bool _eraseR(BSTNode*& root, const K& key) { if (root == nullptr) { return false; } if (key < root->_key) { return _eraseR(root->_left, key); } else if (key > root->_key) { return _eraseR(root->_right, key); } else { //相等了，需要进行删除了 BSTNode* del = root; if (root->_left == nullptr)//左为空 { root = root->_right; } else if (root->_right == nullptr)//右为空 { root = root->_left; } else//左右都不为空 { BSTNode* parent = root; BSTNode* leftmax = root->_left;//找到左孩子中最大的那个 while (leftmax->_right) { parent = leftmax; leftmax = leftmax->_right; } std::swap(root->_key, leftmax->_key); return _eraseR(root->_left, key); } delete del; del = nullptr; return true; } } //析构子函数 void Destruction(BSTNode*& root) { if (root == nullptr) { return; } //先去释放左孩子和右孩子的空间资源 Destruction(root->_left); Destruction(root->_right); //再去释放root自己的空间资源 delete root; root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝 return; } //拷贝构造函数的子函数(写法一) void Construct(BSTNode*& root, BSTNode* copy) { if (copy == nullptr) { root = nullptr; return; } root = new BSTNode(copy->_key); Construct(root->_left, copy->_left); Construct(root->_right, copy->_right); } //拷贝构造子函数(写法二) BSTNode* Construct(BSTNode* root) { if (root == nullptr) { return nullptr; } BSTNode* newnode = new BSTNode(root->_key); newnode->_left = Construct(root->_left); newnode->_right = Construct(root->_right); return newnode; } public: BinarySearchTree() :_root(nullptr) {} //拷贝构造(写法一) /*BinarySearchTree(const Self& tree) :_root(nullptr) { Construct(_root, tree._root); }*/ //拷贝构造(写法二) BinarySearchTree(const Self& tree) { _root = Construct(tree._root); } //赋值运算符重载(现代写法) Self& operator=(Self tree) { swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点 return *this; } //插入(非递归) bool insert(const K& key, const V& val) { if (_root == nullptr) { _root = new BSTNode(key, val); return true; } BSTNode* newnode = new BSTNode(key, val); BSTNode* cur = _root; BSTNode* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false;//相等就说明树中已经有了，就应该插入失败 } } //if (parent->_left == cur)//左右都是空，每次就走上面这个了 if (key < parent->_key) { parent->_left = newnode; } else { parent->_right = newnode; } return true; } //插入(递归) bool InsertR(const K& key, const V& val) { return _InsertR(_root, key, val); } //中序遍历 void InOrder() { _InOrder(_root); cout << endl; } //查找(非递归) BSTNode* find(const K& key) { BSTNode* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return cur; } } return nullptr; } //查找(递归) BSTNode* FindR(const K& key) { return _FindR(_root, key); } //删除(非递归) bool erase(const K& key) { BSTNode* cur = _root; BSTNode* parent = nullptr; //先找需要删除的结点 while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { //到这里说明cur就是待删除的节点 if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤 { if (parent == nullptr) { _root = _root->_right; } else if (cur == parent->_left)//判断cur是左孩子还是右孩子 { parent->_left = cur->_right; } else if (cur == parent->_right) { parent->_right = cur->_right; } } else if (cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子) { if (parent == nullptr) { _root = _root->_left; } else if (cur == parent->_left)//判断cur是左孩子还是右孩子 { parent->_left = cur->_left; } else if (cur == parent->_right) { parent->_right = cur->_left; } } else//到这里说明cur有两个孩子 { BSTNode* parent = cur; BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个 while (leftmax->_right) { parent = leftmax; leftmax = leftmax->_right; } std::swap(cur->_key, leftmax->_key); cur = leftmax; //有一种极端情况就是左边只有一条路径 if (leftmax == parent->_left) { parent->_left = leftmax->_left; } else { parent->_right = leftmax->_left; } } delete cur; return true; } } return false; } //删除递归版 bool eraseR(const K& key) { return _eraseR(_root, key); } //析构函数 ~BinarySearchTree() { Destruction(_root); } private: BSTNode* _root = nullptr; }; } void TestBSTree4() { // 统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" }; K_V::BinarySearchTree<string, int> countTree; for (const auto& str : arr) { // 先查找水果在不在搜索树中 // 1、不在，说明水果第一次出现，则插入<水果, 1> // 2、在，则查找到的节点中水果对应的次数++ //BSTreeNode<string, int>* ret = countTree.Find(str); auto ret = countTree.FindR(str); if (ret == NULL) { countTree.insert(str, 1); } else { ret->_val++; } } countTree.InOrder(); }
小Tips：虽然变成了 KV 模型，但它仍然是一颗二叉搜索树，因此整棵树的结构没有发生任何变化。唯一的变化在于树的结点，对与 KV 模型来说，树中的结点不仅要存 Key，还要存 Value，这就进一步导致在插入时不仅要插入 Key，还要插入一个与该 Key 对应的 Value。其次对 KV 模型来说，Key 不允许被修改，Value 可以被修改，因此对 KV 模型来说，在 Find 的时候应该返回结点的指针，这样方便后续进行一些操作。
五、二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二插搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。
- 最优情况下：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：l o g 2 n log2^nlog2n。
- 最差情况下：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为：N 2 \frac{N}{2}2N。如果退化成了单支树，那么二叉搜索树的性能就失去了。此时就需要用到即将登场的 AVL 树和红黑树了。
六、结语
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！
