最典型的一个场景，自动翻译软件，输入中文，输出对应的英文，输入英文，输出对应的中文。
可以用一颗搜索二叉树来实现这一功能。
K->key V->val
基础结构和普通搜索二叉树保持一致，只是成员多了一个_val，模板也多了一个参数V。
还不知道二叉搜索树的可以看我另外一篇博客。
namespace kv { template<class K, class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; K _key; V _value; BSTreeNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; 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) { //... return true; } 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; };
测试一下功能：
如果要实现一个统计单词个数的呢？
那么就构造一个
<string,int>类型的就好了，string记录单词，int记录个数。
void TestBSTree2() { string arr[] = { "香蕉", "苹果", "香蕉", "草莓", "香蕉", "苹果", "苹果", "苹果" }; BSTree<string, int> countTree; for (auto& str : arr) { //BSTreeNode<string, int>* ret = countTree.Find(str); auto ret = countTree.Find(str); if (ret) { ret->_value++; } else { countTree.Insert(str, 1); } } countTree.InOrder(); }
总和代码：
#include<iostream> using namespace std; namespace kv { template<class K, class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; K _key; V _value; BSTreeNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; 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) { //... return true; } 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 TestBSTree1() { BSTree<string, string> dict; dict.Insert("sort", "排序"); dict.Insert("left", "左边"); dict.Insert("right", "右边"); dict.Insert("string", "字符串"); dict.Insert("insert", "插入"); string str; while (cin >> str) { BSTreeNode<string, string>* ret = dict.Find(str); if (ret) { cout << "对应的中文:" << ret->_value << endl; } else { cout << "对应的中文->无此单词" << endl; } } } void TestBSTree2() { string arr[] = { "香蕉", "苹果", "香蕉", "草莓", "香蕉", "苹果", "苹果", "苹果" }; BSTree<string, int> countTree; for (auto& str : arr) { //BSTreeNode<string, int>* ret = countTree.Find(str); auto ret = countTree.Find(str); if (ret) { ret->_value++; } else { countTree.Insert(str, 1); } } countTree.InOrder(); } }
