首先模拟一下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;

这样拷贝构造就可以正常运行了