运用主要是搜索二叉树<K,V>模版
SBtree.h:
namespace hush1
{template<class K,class V>struct STnode{K _key;V _val;struct STnode<K, V>* left;struct STnode<K, V>* right;STnode(const K&key,const V&val):_key(key),_val(val),left(nullptr),right(nullptr){}};template<class K,class V>class Tree{typedef struct STnode<K, V> node;public:Tree() :root(nullptr){}Tree(const Tree<K, V>& t)//拷贝构造函数{root = copy(t.root);}Tree<K, V>& operator=(const Tree<K, V>& t){if (this != &t){destory(root);root = copy(t.root);}return *this;}bool _insert(const K& key, const V& val){try{if (root == nullptr) {root = new node(key, val);return true;}node* cur = root;node* parent = nullptr;while (cur){parent = cur;if (cur->_key > key){cur = cur->left;}else if (cur->_key < key){cur = cur->right;}else{return false;//当你找到相同直接就失败了}}cur = new node(key, val);(parent->_key > key) ? (parent->left = cur) : (parent->right = cur);return true;}catch (const std::exception& e){cout << "捕获异常" << " : ";cout << e.what() << endl;}}bool find(const K& key,V& val){node* cur = root;while (cur){if (cur->_key > key){cur = cur->left;}else if (cur->_key < key){cur = cur->right;}else{val = cur->_val;return true;}}return false;}node* findmin(node* root){while (root->left!= nullptr){root = root->left;}return root;}void inorder(){_inorder(root);}bool Erase(const K& key){return erase(root, key);}~Tree(){destory(root);}private:node* erase(node* &root,const K& key){if (root == nullptr)return nullptr;if (root->_key > key){return erase(root->left, key);}else if (root->_key < key){return erase(root->right, key);}else{if (root->left == nullptr){node* tmp = root->right;delete root;root = tmp;}if (root->right == nullptr){node* tmp = root->left;delete root;root = tmp;}// 左右子节点都不为空，找到右子树中的最小键节点// 将其键值复制到当前节点，然后递归删除右子树中的最小键节点if (root->left != nullptr && root->right != nullptr){node* tmp = findmin(root->right);root->_key = tmp->_key;root->_val = tmp->_val;root->right= erase(root->right, tmp->_key);}return root;}}void _inorder(node*&root){if (root == nullptr)return;_inorder(root->left);cout << "key: " << root->_key << "val: " << root->_val << " ";_inorder(root->right);}void destory(node*& root){if (root == nullptr)return;destory(root->left);destory(root->right);delete root;root = nullptr;}node* copy(node* t){//拷贝主要进行一个空间的申请if (root == nullptr)return nullptr;node* newnode = new node(t->_key, t->_val);newnode->left = copy(t->left);newnode->right = copy(t->right);return newnode;}node* root = nullptr;};
}
// 定义商品类
class Product
{
public:std::string name; // 商品名称double price; // 商品价格int stock; // 商品库存数量// 构造函数，用于初始化商品对象// 接收商品名称、价格和库存数量作为参数Product(const std::string& n, double p, int s) : name(n), price(p), stock(s) {}//在这里string要引用是因为string是类类型 ，拷贝构造开销太大了，所以加引用，int 和double是基本类型// 重载输出运算符，方便打印商品信息// 允许使用 std::cout 直接输出商品对象的信息friend std::ostream& operator<<(std::ostream& os, const Product& product) {os << "Name: " << product.name << ", Price: " << product.price << ", Stock: " << product.stock;return os;}
};T.cpp:
void test_kv()
{// 创建一个键为商品编号（int），值为商品对象（Product）的二叉搜索树hush1::Tree<int, Product> productTree;// 插入商品// 插入商品编号为 1 的商品信息productTree._insert(1, Product("iPhone 14", 999.99, 100));// 插入商品编号为 2 的商品信息productTree._insert(2, Product("MacBook Pro", 1999.99, 50));// 插入商品编号为 3 的商品信息productTree._insert(3, Product("iPad Air", 599.99, 200));// 显示所有商品std::cout << "All products:" << std::endl;productTree.inorder(); // 调用中序遍历函数输出所有商品信息// 查找商品Product foundProduct("", 0, 0); // 用于存储找到的商品信息if (productTree.find(2, foundProduct)) {// 若找到商品编号为 2 的商品，输出其信息std::cout << "Found product with ID 2: " << foundProduct << std::endl;}else {// 若未找到，输出提示信息std::cout << "Product with ID 2 not found." << std::endl;}// 更新商品信息if (productTree.find(2, foundProduct)) {foundProduct.stock = 60; // 更新商品编号为 2 的商品的库存数量productTree.Erase(2); // 先删除原商品信息productTree._insert(2, foundProduct); // 再插入更新后的商品信息std::cout << "Updated product with ID 2: " << foundProduct << std::endl;}// 删除商品if (productTree.Erase(3)) {// 若成功删除商品编号为 3 的商品，输出提示信息std::cout << "Product with ID 3 deleted." << std::endl;}else {// 若未找到该商品，输出提示信息std::cout << "Product with ID 3 not found." << std::endl;}// 显示更新后的所有商品std::cout << "All products after update:" << std::endl;productTree.inorder(); // 调用中序遍历函数输出更新后的所有商品信息}int main()
{test_kv();return 0;
}
