首先模拟一下key形式类 使用的结构是搜索二叉树 结点中有左孩子和右孩子 还有一个存储的值
template <class K>struct BSTnode//搜索二叉树不支持修改 中序遍历是有序的{K _key;BSTnode<K>* _left;BSTnode<K>* _right;BSTnode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};这里二叉树代码在之前有更详细的 也有测试代码 就不去复制了
主要功能有四个 删除 插入 遍历 查找
模拟一下key/value形式类 使用的结构是搜索二叉树 每一个节点中有左孩子和右孩子 还有一个key 和一个value 当我们找到可以key之后 也就找到了对应的value
template <class K, class V>
struct BSTnode//搜索二叉树不支持修改 中序遍历是有序的
{K _key;V _value;BSTnode<K, V>* _left;BSTnode<K, V>* _right;BSTnode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}
};之后二叉树的功能有插入 删除 查找 遍历 这其中只有insert 需要修改 既要插入value 也要插入key 但对于删除 查找 遍历 只要有key就可以完成 所以就不需要改变
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;
}这里通过一段string类型的进行测试
int main()
{keyvalue::BSTree <string, string> tt;tt.insert("left","左边");tt.insert("right", "右边");tt.insert("insert", "插入");tt.insert("string", "字符串");string str;while (cin >> str){auto ret = tt.find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词 请重新输入" << endl;}}//tt.insert();return 0;
}
通过查找key 就可以确定对应的存储value内容 非常方便 这里最后使用的是ctrl+z来结束程序执行
这里使用到了 operator>>（string）这个函数的返回值istream 会被operator bool 转换成bool值来进行判断是否结束程序 而当我们输入ctrl+z 就会转换成bool值false 这样就会结束程序
首先模拟一下key形式类 使用的结构是搜索二叉树 结点中有左孩子和右孩子 还有一个存储的值
template <class K>struct BSTnode//搜索二叉树不支持修改 中序遍历是有序的{K _key;BSTnode<K>* _left;BSTnode<K>* _right;BSTnode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};这里二叉树代码在之前有更详细的 也有测试代码 就不去复制了
主要功能有四个 删除 插入 遍历 查找
模拟一下key/value形式类 使用的结构是搜索二叉树 每一个节点中有左孩子和右孩子 还有一个key 和一个value 当我们找到可以key之后 也就找到了对应的value
template <class K, class V>
struct BSTnode//搜索二叉树不支持修改 中序遍历是有序的
{K _key;V _value;BSTnode<K, V>* _left;BSTnode<K, V>* _right;BSTnode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}
};之后二叉树的功能有插入 删除 查找 遍历 这其中只有insert 需要修改 既要插入value 也要插入key 但对于删除 查找 遍历 只要有key就可以完成 所以就不需要改变
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;
}这里通过一段string类型的进行测试
int main()
{keyvalue::BSTree <string, string> tt;tt.insert("left","左边");tt.insert("right", "右边");tt.insert("insert", "插入");tt.insert("string", "字符串");string str;while (cin >> str){auto ret = tt.find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词 请重新输入" << endl;}}//tt.insert();return 0;
}
通过查找key 就可以确定对应的存储value内容 非常方便 这里最后使用的是ctrl+z来结束程序执行
这里使用到了 operator>>（string）这个函数的返回值istream 会被operator bool 转换成bool值来进行判断是否结束程序 而当我们输入ctrl+z 就会转换成bool值false 这样就会结束程序
这里的key/value除了可以运用在字典序中 还可以运用在计数上
int main()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };keyvalue::BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.find(str);if (ret == NULL){countTree.insert(str, 1);}else{ret->_value++;}}countTree.inorder();return 0;
}
接下来我们写一下二叉树的析构
~BSTree()
{destroy(_root);_root = nullptr;
}void destroy(node*root){if (root == nullptr)return;destroy(root->_left);destroy(root->_right);delete root;}这里需要用到destroy函数这是因为析构函数是没有参数的 而二叉树的析构有需要用到参数 所以嵌套了一个destroy函数 这里使用的是递归 先销毁左边 在销毁右节点 最后销毁跟节点
接下来写一下 拷贝构造
由于我们现在没有写拷贝构造 使用的是浅拷贝 会出问题
int main()
{keyvalue::BSTree <string, string> tt;tt.insert("left","左边");tt.insert("right", "右边");tt.insert("insert", "插入");tt.insert("string", "字符串");keyvalue::BSTree<string, string> t(tt);return 0;
}
这时代码是会崩溃的
BSTree(const BSTree<K,V>& t)
{_root = copy(t._root);
}
node* copy(node* root){if (root == nullptr){return 0;}node* newroot = new node(root->_key, root->_value);newroot->_left = copy(root->_left);newroot->_right = copy(root->_right);return newroot;}这里同样需要传参 所以进行了嵌套copy函数 这里如果二叉树为空就返回 如果不为空 开始拷贝 从根节点开始首先赋值 之后链接对应左右孩子 这里左右孩子的拷贝通过递归完成
写完成之后运行会出问题
这是因为没有默认构造函数 这里我们写一个比较快捷的方式
BSTree() = default;
这样拷贝构造就可以正常运行了
