map和set（一）

首先模拟一下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来结束程序执行

这里的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函数这里如果二叉树为空就返回如果不为空开始拷贝从根节点开始首先赋值之后链接对应左右孩子这里左右孩子的拷贝通过递归完成

写完成之后运行会出问题