#pragma once #includeusing namespace std; template struct BsTreeNode{//二叉树 节点 K _key; V _value; BsTreeNode* _left; BsTreeNode* _right; BsTreeNode(const K& key,const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) {} }; template class BsTree{ public: typedef BsTreeNode Node; BsTree() : _root(NULL) { } ~BsTree(){} bool Insert(const K& key, const V& value)//插入 非递归 { if (_root == NULL){ _root = new Node(key, value); return true; } Node* cur = _root; while (1){ if (cur->_key > key) { if (cur->_left) cur = cur->_left; else{ cur->_left = new Node(key, value); return true; } } else if (cur->_key < key) { if (cur->_right) cur = cur->_right; else{ cur->_right = new Node(key, value); return true; } }//以上为找 插入位置 并插入 else if (cur->_key == key)//存在 插入失败 return false; } } bool InsertR(const K& key,const V& value)//插入 递归 { return _InsertR(_root,key,value); } Node* Find(const K& key){//查找 Node * cur = _root; while (cur){ if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return cur; } return NULL; } bool RemoveR(const K& key)//删除 递归 { if (_root == NULL) return false; return _RemoveR(_root,key); } bool Remove(K key){//删除 非递归 Node* cur=_root, *prev=NULL; while (cur){ if (cur->_key > key) { prev = cur; cur = cur->_left; } else if (cur->_key < key) { prev = cur; cur = cur->_right; }// 以上为 找到要删除的 节点 else { if (cur->_left == NULL)//如果节点左或右为空,直接删除该节//点将之后的节点 连接在其父节点 { if (prev == NULL) { _root = cur->_right; } else if (prev->_left == cur) { prev->_left = cur->_right; } else prev->_right = cur->_right; } else if (cur->_right == NULL)//同上 右为空 { if (prev == NULL) { _root = cur->_left; delete cur; } else if (prev->_right == cur) { prev->_right = cur->_left; } else prev->_left = cur->_left; } else//如果左右都不为空 找右孩子最左 或 左孩子最右 节点替 //代删除 { prev = cur; cur = cur->_right; while (cur->_left){ cur = cur->_left; } prev->_key = cur->_key; prev->_value = cur->_value; prev->_right =cur->_right; } delete cur; return true; } } return false; } bool modification(K key,V value){//修改 Node* ret = Find(key); if (ret == NULL) return false; ret->_value = value; return true; } private: bool _InsertR(Node* & root,const K& key,const V& value)//插入 递归函数 { if (root == NULL) { root = new Node(key,value); return true; } if (root->_key == key) return false; else if (root->_key > key) return _InsertR(root->_left,key,value); else return _InsertR(root->_right,key,value); } bool _RemoveR(Node* & root,const K& key)//删除 递归函数 { if (root->_key < key) return _RemoveR(root->_right, key); if (root->_key>key) return _RemoveR(root->_left, key); if (root->_left == NULL) { Node* dev = root; root = root->_right; delete dev; return true; } else if (root->_right == NULL) { Node* dev = root; root = root->_left; delete dev; return true; } else { root->_key = root->_right->_key; root->_value = root->_right->_value; return _RemoveR(root->_right,root->_key); } } Node* _root; };