五、K模型和KV模型搜索树

1.K模型搜索树

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。K模型不存在重复值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

（1）以单词集合中的每个单词作为key，构建一棵二叉搜索树

（2）在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

1. #pragma once
2. #include<iostream>
3. using namespace std;
4. 
5. namespace K
6. {
7.  //树的节点可以支持多种类型
8.  template<class K>
9.  //树节点结构
10.   struct BSTreeNode
11.   {
12.     BSTreeNode<K>* _left;//左指针
13.     BSTreeNode<K>* _right;//右指针
14.     K _key;//值
15. 
16.     //构造函数
17.     BSTreeNode(const K& key)
18.       :_left(nullptr)
19.       , _right(nullptr)
20.       , _key(key)
21.     {}
22.   };
23. 
24.   template<class K>
25.   class BStree//树结构
26.   {
27.     typedef BSTreeNode<K> Node;
28.   private:
29.     //查找
30.     Node* _FindR(Node* root, const K& key)
31.     {
32.       if (root == nullptr)//没找到
33.       {
34.         return nullptr;
35.       }
36. 
37.       if (key < root->_key)//到左子树去找
38.       {
39.         FindR(root->_left, key);
40.       }
41.       else if (key > root->_key)//到右子树去找
42.       {
43.         FindR(root->_right, key);
44.       }
45.       else//找到了
46.       {
47.         return root;
48.       }
49.     }
50. 
51.     //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
52.     bool _InsertR(Node*& root, const K& key)
53.     {
54.       if (root == nullptr)//找到位置了
55.       {
56.         root = new Node(key);
57.         return true;
58.       }
59.       if (key < root->_key)//到左子树去找位置
60.       {
61.         _InsertR(root->_left, key);
62.       }
63.       else if (key > root->_key)//到右子树去找位置
64.       {
65.         _InsertR(root->_right, key);
66.       }
67.       else//已存在，无需插入
68.       {
69.         return false;
70.       }
71.     }
72. 
73.     bool _EraseR(Node*& root, const K& key)
74.     {
75.       if (root == nullptr)//没找到
76.       {
77.         return false;
78.       }
79.       if (key < root->_key)//到左子树去找
80.       {
81.         _EraseR(root->_left, key);
82.       }
83.       else if (key > root->_key)//到右子树去找
84.       {
85.         _EraseR(root->_right, key);
86.       }
87.       else
88.       {
89.         //找到了，root就是要删除的节点
90.         if (root->_left == nullptr)//root左为空
91.         {
92.           Node* del = root;
93.           root = root->_right;
94.           delete del;
95.         }
96.         else if (root->_right == nullptr)//root右为空
97.         {
98.           Node* del = root;
99.           root = root->_left;
100.          delete del;
101.        }
102.        else//root左右都不为空
103.        {
104.          //找右子树最左节点
105.          Node* minRight = root->_right;
106.          while (minRight->_left)
107.          {
108.            minRight = minRight->_left;
109.          }
110. 
111.          //保存右子树最左节点的值
112.          K min = minRight->_key;
113. 
114.          //使用递归方法删除右子树最左节点
115.          _Erase(root->_right, min);
116.        }
117.        return true;
118.      }
119.    }
120. 
121.    Node* _copy(Node* root)
122.    {
123.      if (root == nullptr)//如果根为空，直接返回
124.      {
125.        return;
126.      }
127. 
128.      Node* copyNode = new Node(root->_key);//创建根节点
129.      copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
130.      copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
131. 
132.      return copyNode;//返回根
133.    }
134. 
135.    _Destroy(root)
136.    {
137.      if (root == nullptr)
138.      {
139.        return;
140.      }
141.      _Destroy(root->_left);
142.      _Destroy(root->_right);
143.      delete root;
144.    }
145.  public:
146.    //构造函数需要将根初始化为空就行了
147.    BSTree()
148.      :_root(nullptr)
149.    {}
150. 
151.    //拷贝构造
152.    BSTree(const BSTree<K>& t)
153.    {
154.      _root = t.copy(t._root);
155.    }
156. 
157.    //赋值运算符重载(现代写法)
158.    BSTree& operator=(const BSTree<K>& t)
159.    {
160.      swap(_root, t._root);
161.      return *this;
162.    }
163. 
164.    //析构
165.    ~BSTree()
166.    {
167.      _Destroy(_root);
168.      _root = nullptr;
169.    }
170. 
171.    //中序遍历
172.    void _Inorder(Node* root)
173.    {
174.      if (root == nullptr)
175.      {
176.        return;
177.      }
178.      _Inorder(root->_left);//递归调用自己
179.      cout << root->_key << " ";
180.      _Inorder(root->_right);//递归调用自己
181.    }
182. 
183.    //先调不传参数的InOrder
184.    void InOrder()
185.    {
186.      //把_root传给子函数，让子函数去使用_root
187.      _InOrder(_root);
188.      cout << endl;
189.    }
190.  public:
191.    //递归查找
192.    Node* FindR(const K& key)
193.    {
194.      return _FindR(_root, key);
195.    }
196. 
197.    //递归插入
198.    bool InsertR(const K& key)
199.    {
200.      return _InsertR(_root, key);
201.    }
202. 
203.    //递归删除
204.    bool EraseR(const K& key)
205.    {
206.      return _EraseR(_root, key);
207.    }
208.  private:
209.    Node* _root;
210.  };
211. }

2.KV模型搜索树

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：

（1）<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key。

（2）查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。

KV模型可以插入重复值，在K模型的基础上，节点增加了_value成员，用来_key去查找_value，_value的类型不确定，再增加一个模板参数即可：

1. namespace KV
2. {
3.  //树的节点可以支持多种类型
4.  template<class K, class V>
5.  //树节点结构
6.  struct BSTreeNode
7.  {
8.    BSTreeNode<K,V>* _left;//左指针
9.    BSTreeNode<K,V>* _right;//右指针
10.     K _key;
11.     V _value;//增加了_value成员
12. 
13.     //构造函数
14.     BSTreeNode(const K& key)
15.       :_left(nullptr)
16.       , _right(nullptr)
17.       , _key(key)
18.       ,_value(value)//初始化_value成员
19.     {}
20.   };
21. 
22.   template<class K, class V>//模板类型从K变成了KV
23.   class BStree//树结构
24.   {
25.     typedef BSTreeNode<K,V> Node;//模板类型从K变成了KV
26.   private:
27.     //查找
28.     Node* _FindR(Node* root, const K& key)
29.     {
30.       if (root == nullptr)//没找到
31.       {
32.         return nullptr;
33.       }
34. 
35.       if (key < root->_key)//到左子树去找
36.       {
37.         FindR(root->_left, key);
38.       }
39.       else if (key > root->_key)//到右子树去找
40.       {
41.         FindR(root->_right, key);
42.       }
43.       else//找到了
44.       {
45.         return root;
46.       }
47.     }
48. 
49.     //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲
50.     bool _InsertR(Node*& root, const K& key, const V& value)//增加了_value成员
51.     {
52.       if (root == nullptr)//找到位置了
53.       {
54.         root = new Node(key, value);
55.         return true;
56.       }
57.       if (key < root->_key)//到左子树去找位置
58.       {
59.         _InsertR(root->_left, key, value);
60.       }
61.       else if (key > root->_key)//到右子树去找位置
62.       {
63.         _InsertR(root->_right, key, value);
64.       }
65.       else//已存在，无需插入
66.       {
67.         return false;
68.       }
69.     }
70. 
71.     bool _EraseR(Node*& root, const K& key,const V& value)//增加了_value成员
72.     {
73.       if (root == nullptr)//没找到
74.       {
75.         return false;
76.       }
77.       if (key < root->_key)//到左子树去找
78.       {
79.         _EraseR(root->_left, key, value);
80.       }
81.       else if (key > root->_key)//到右子树去找
82.       {
83.         _EraseR(root->_right, key, value);
84.       }
85.       else
86.       {
87.         //找到了，root就是要删除的节点
88.         if (root->_left == nullptr)//root左为空
89.         {
90.           Node* del = root;
91.           root = root->_right;
92.           delete del;
93.         }
94.         else if (root->_right == nullptr)//root右为空
95.         {
96.           Node* del = root;
97.           root = root->_left;
98.           delete del;
99.         }
100.        else//root左右都不为空
101.        {
102.          //找右子树最左节点
103.          Node* minRight = root->_right;
104.          while (minRight->_left)
105.          {
106.            minRight = minRight->_left;
107.          }
108. 
109.          //保存右子树最左节点的值
110.          K kMin = minRight->_key;
111.          V vMin = minRight->value;//增加了_value成员
112. 
113.          //使用递归方法删除右子树最左节点
114.          _Erase(root->_right, kMin);
115.          root->_key = kMin;
116.          root->_value = vMin;//增加了_value成员
117.        }
118.        return true;
119.      }
120.    }
121. 
122.    Node* _copy(Node* root)
123.    {
124.      if (root == nullptr)//如果根为空，直接返回
125.      {
126.        return nullptr;
127.      }
128. 
129.      Node* copyNode = new Node(root->_key,root->_value);//创建根节点，增加了_value成员
130.      copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
131.      copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
132. 
133.      return copyNode;//返回根
134.    }
135. 
136.    _Destroy(root)
137.    {
138.      if (root == nullptr)
139.      {
140.        return;
141.      }
142.      _Destroy(root->_left);
143.      _Destroy(root->_right);
144.      delete root;
145.    }
146.  public:
147.    //构造函数需要将根初始化为空就行了
148.    BSTree()
149.      :_root(nullptr)
150.    {}
151. 
152.    //拷贝构造
153.    BSTree(const BSTree<K>& t)
154.    {
155.      _root = t.copy(t._root);
156.    }
157. 
158.    //赋值运算符重载(现代写法)
159.    BSTree& operator=(const BSTree<K>& t)
160.    {
161.      swap(_root, t._root);
162.      return *this;
163.    }
164. 
165.    //析构
166.    ~BSTree()
167.    {
168.      _Destroy(_root);
169.      _root = nullptr;
170.    }
171. 
172.    //中序遍历
173.    void _Inorder(Node* root)
174.    {
175.      if (root == nullptr)
176.      {
177.        return;
178.      }
179.      _Inorder(root->_left);//递归调用自己
180.      cout << root->_key << ":" << root->_value<<endl;//增加了_value成员
181.      _Inorder(root->_right);//递归调用自己
182.    }
183. 
184.    //先调不传参数的InOrder
185.    void InOrder()
186.    {
187.      //把_root传给子函数，让子函数去使用_root
188.      _InOrder(_root);
189.      cout << endl;
190.    }
191.  public:
192.    //递归查找
193.    Node* FindR(const K& key)
194.    {
195.      return _FindR(_root, key);
196.    }
197. 
198.    //递归插入
199.    bool InsertR(const K& key,const V& value)//增加了_value成员
200.    {
201.      return _InsertR(_root, key, value);
202.    }
203. 
204.    //递归删除
205.    bool EraseR(const K& key)
206.    {
207.      return _EraseR(_root, key);
208.    }
209.  private:
210.    Node* _root;
211.  };
212. }