1.⼆叉搜索树的概念
⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
•
若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
•
若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
•
它的左右⼦树也分别为⼆叉搜索树
2.二叉搜索树的模拟实现：
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string.h> using namespace std; template<class K, class V> struct BSTreeNode { K _key; V _value; BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; BSTreeNode(const K& key, const V& value) :_key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} }; template<class K, class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool Insert(const K& key, const V& value) { if (_root == nullptr) { _root =new Node(key, value); 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, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* 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 cur; } } return nullptr; } 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->_left == nullptr) { 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* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) { replaceParent = replace; replace = replace->_left; } cur->_key = replace->_key; if (replaceParent->_left == replace) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; } return true; } } return false; } void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right); } private: Node* _root = nullptr; }; void TestBSTree() { /*BSTree<string, string> dict; dict.Insert("insert", "插入"); dict.Insert("erase", "删除"); dict.Insert("left", "左边"); dict.Insert("string", "字符串"); string str; while (cin >> str) { auto ret = dict.Find(str); if (ret) { cout << str << ":" << ret->_value << endl; } else { cout << "单词拼写错误" << endl; } }*/ string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" }; // 统计水果出现的次 BSTree<string, int> countTree; for (auto str : strs) { auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder(); } int main() { TestBSTree(); return 0; }
