代发货网站建设,久久建筑网的文件是免费下载吗,网站买空间的价格,网站建设需要用到的技术二叉树进阶#xff08;二叉搜索树#xff09; 一、二叉搜索树1.1 二叉搜索树的概念 二、二叉搜索树的结构2.1 结点结构2.2 树结构 三、二叉搜索树的操作#xff08;非递归#xff09;3.1 二叉搜索树的插入3.2 二叉搜索树的查找3.3 二叉搜索树的中序遍历3.4 二叉搜索树的删除… 二叉树进阶二叉搜索树 一、二叉搜索树1.1 二叉搜索树的概念 二、二叉搜索树的结构2.1 结点结构2.2 树结构 三、二叉搜索树的操作非递归3.1 二叉搜索树的插入3.2 二叉搜索树的查找3.3 二叉搜索树的中序遍历3.4 二叉搜索树的删除 四、二叉搜索树的操作递归4.1 二叉搜索树的查找4.2 二叉搜索树的插入4.3 二叉搜索树的删除 五、其他相关成员函数的实现5.1 析构函数5.2 构造和拷贝构造5.3 赋值重载 6、二叉搜索树的应用6.1 K模型6.2 KV模型6.3 KV模型代码实现6.3.1 将二叉搜索树循环版本改为KV模型6.3.2 映射--通过key的值找value6.3.3 统计水果出现的次数 七、二叉搜索树的性能分析八、完整代码8.1 BSTree.h8.1 test.cpp 一、二叉搜索树
1.1 二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 基本属性 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 衍生属性 二叉搜索树不支持修改因为修改之后会改变二叉搜索树的条件使其变成非二叉搜索树。 二叉搜索树不能有重复的值不支持重复值的搜索。在插入的时候会做到自动去重。 二叉搜索树的中序遍历Inorder是升序的。 二、二叉搜索树的结构
首先我们定义以下结点和搜索二叉树的结构我们之前定义一个模板类一般都喜欢用Ttype但是在这里比较喜欢用Kkey
2.1 结点结构
templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};2.2 树结构
templateclass Kclass BSTree{typedef BSTreeNodeK Node;public://....}三、二叉搜索树的操作非递归
3.1 二叉搜索树的插入
插入的具体过程如下 a树为空则直接新增结点赋值给root指针 b树不为空按二叉搜索树性质查找插入位置插入新结点 bool Insert(const K key){if (_root nullptr){_root new Node(key);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);//链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}3.2 二叉搜索树的查找 a从根开始比较查找比根大则往右边走查找比根小则往左边走查找 b最多查找高度次走到空还没找到这个值不存在 bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}3.3 二叉搜索树的中序遍历
对于二叉搜索树而言每一个结点的左子树值都比该结点的值小右子树的值都比该结点的值要大。所以中序遍历二叉搜索树是可以得到一个升序序列的。 void InOrder(){_InOrder(_root);cout endl;}//void _InOrder(Node* root_root) // 1.缺省值必须是全局变量或者是常量要在类里面访问到 //2.他需要用到this访问成员变量是形参this指针只能在函数内部使用void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}3.4 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况 a要删除的结点无孩子结点 b要删除的结点只有左孩子结点 c要删除的结点只有右孩子结点 d要删除的结点右左、右孩子结点 看起来有待删除结点有4种情况实际情况a可以与情况b或者c合并起来 b右子树为空 c左子树为空 d左右子树都不为空 因此真正的删除过程如下 情况b删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点–直接删除 情况c删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在它的右子树中寻找中序下的第一个结点关键码最小右子树的最左值也就是右子树最小结点用它的值填补到被删除结点中再来处理该结点的删除问题–替换法删除 情况a
情况b和情况c
情况d
四、二叉搜索树的操作递归
4.1 二叉搜索树的查找 查找就是从根结点开始如果大于根结点的值就转换为右子树里面查找如果小于根结点就转换为去左子树查找如果等于就直接返回那对于子树也是这样一步步转换为子问题。 如果最后都没找到一直到空那就返回false bool _FindR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}bool FinR(const K key){return _FindR(_root, key);}4.2 二叉搜索树的插入 从根结点开始如果要插入的结点大于根就转换为去右子树插入如果要插入的结点小于根就转换为去左子树插入如果相等返回false如果一直走到空那就在该位置插入就行了。 但是有一个问题我们找到空插入的时候如何和它的父亲链接起来 直接用root的引用就可以了。 因为引用的话走到空他就是那个位置指针的引用直接赋给它就链接上了。 还不用像上面循环实现的那样去判断要链接到哪边 那大家思考一下我们上面循环的方式可以用引用吗 不可以的因为C中的引用时不能改变指向的引用一旦引用一个实体之后就不能再引用其他实体 而这里递归的话每次递归都相当于创建了一个新的引用而不是改变上一层的引用的指向。 比如要往左子树插入值此时root为空new一个节点插入值root这个节点就是父节点的左指针的引用如果没有加这个引用那么修改函数里的指针并不会影响函数外面的指针即使new了节点外面父节点的指针还是指向空不会受影响。而加了引用root就是父节点指向左子树这个指针的别名此时修改root就相当于修改了父节点的左指针 bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool InsertR(const K key){return _InsertR(_root, key);}4.3 二叉搜索树的删除
从根结点开始判断如果要删除的值大于根转换为去右子树删小于根转换为去左子树删相等就进行删除如果走到空那就是找不到。 其实还是我们上面分析的那三种情况 左为空、右为空或者左右都不为空。 那这里我们用引用写起来还是比较简便的。 先写一下左为空和右为空的情况这两个比较好处理 然后看一下比较麻烦的左右都不为空的情况 我们之前非递归版本的实现是找一个符合条件的结点替换它然后把替换的结点删除掉 这里也可以用同样的方法但我觉得比较简便的方法是这样的 还是先找一个可以替代要删除结点的结点左子树最大结点或右子树最小结点以左子树最大结点替换为例 交换它们两个的值然后删除左子树里面的key这个结点就行了 先找到节点删除节点还是分三种情况1.root的左节点为空把root先提前用指针存好然后让root的右节点给自己因为自己是父节点的指针所以就相当于让父节点指向指向root的右节点托孤最后释放掉提前存好的root节点就可以了2.root的右节点为空跟第一个差不多3.root的左右节点都不为空这里用的是交换值然后到root的右子树中去删除原来的key简化问题去处理。 bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;//开始准备删除if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{//找左树的最大节点Node* maxleft root-_left;while (maxleft-_right){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);//_root-_key maxleft-_key; //不能使用赋值只能使用交换return _EraseR(root-_left, key); //转换成在子树去删除//return _EraseR(maxleft, key); //不能使用maxleft不然引用不起作用}delete del;return true;}}bool EraseR(const K key){return _EraseR(_root, key);}五、其他相关成员函数的实现
5.1 析构函数 析构的话我们这里还是用递归来实现也可以用循环但是比较麻烦。对于Destroy最好的做法就是后续销毁。 ~BSTree(){Destroy(_root);//_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}5.2 构造和拷贝构造
深拷贝的拷贝构造我们还是用递归来实现通过先序去拷贝创建就行了 BSTree(const BSTreeK t){_root Copy(t._root);}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}有了拷贝构造之后编译器就不会生成默认的构造函数了那就需要我们呢自己写了。另外C11有一个关键字–default可以强制编译器生成默认构造 有了默认构造我们给了缺省值它就走初始化列表的时候就会用缺省值去初始化。
5.3 赋值重载
赋值重载直接使用现代的写法就可以了
BSTreeK operator(BSTreeK t)
{swap(_root, t._root);return *this;
}6、二叉搜索树的应用
6.1 K模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 a以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树。 b在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
6.2 KV模型
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 a比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 b再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
6.3 KV模型代码实现
6.3.1 将二叉搜索树循环版本改为KV模型
namespace key_value
{templateclass K,class Vstruct BSTreeNode{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _value;BSTreeNode(const K key,const V value):_left(nullptr), _right(nullptr), _key(key),_value(value){}};templateclass K,class Vclass BSTree{typedef BSTreeNodeK,V Node;public:/*BSTree():_root(nullptr){}*/BSTree() default; //指定强制生成默认构造BSTree(const BSTreeK,V t){_root Copy(t._root);}BSTreeK,V operator(BSTreeK,V t){swap(_root, t._root);return *this;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}~BSTree(){Destroy(_root);_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}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;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}bool FinR(const K key){return _FindR(_root, key);}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool InsertR(const K key){return _InsertR(_root, key);}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;//开始准备删除if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* maxleft root-_left;while (maxleft-_right){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);return _EraseR(root-_left, key);//return _EraseR(maxleft, key); //不能使用maxleft不然引用不起作用}delete del;return true;}}bool EraseR(const K key){return _EraseR(_root, key);}bool Erase(const K key){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{//删除//1.左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//找右树最小节点替代也可以是左树最大节点替代Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}//void _InOrder(Node* root_root) 1.缺省值必须是全局变量或者是常量要在类里面访问到 2.他需要用到this访问成员变量是形参this指针只能在函数内部使用void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
}6.3.2 映射–通过key的值找value
void TestBSTree2()
{key_value::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(left, 左边);dict.Insert(right, 右边);dict.Insert(string, 字符串);dict.Insert(insert, 插入);dict.Insert(erase, 删除);string str;while (cin str){auto ret dict.Find(str);if (ret){cout : ret-_value endl;}else{cout 无此单词 endl;}}}6.3.3 统计水果出现的次数
void TestBSTree3()
{// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };key_value::BSTreestring, int countTree;for (auto str : arr){//key_value::BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}七、二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N
八、完整代码
8.1 BSTree.h
#pragma once//BinarySearchTree -- BSTree
//SearchBinaryTreenamespace key
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:/*BSTree():_root(nullptr){}*/BSTree() default; //指定强制生成默认构造BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}~BSTree(){Destroy(_root);//_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}bool Insert(const K key){if (_root nullptr){_root new Node(key);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);//链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}bool FinR(const K key){return _FindR(_root, key);}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool InsertR(const K key){return _InsertR(_root, key);}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;//开始准备删除if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{//找左树的最大节点Node* maxleft root-_left;while (maxleft-_right){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);//_root-_key maxleft-_key; //不能使用赋值只能使用交换return _EraseR(root-_left, key); //转换成在子树去删除//return _EraseR(maxleft, key); //不能使用maxleft不然引用不起作用}delete del;return true;}}bool EraseR(const K key){return _EraseR(_root, key);}bool Erase(const K key){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{//删除//1.左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//找右树最小节点替代也可以是左树最大节点替代Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}//protected://void _InOrder(Node* root_root) 1.缺省值必须是全局变量或者是常量要在类里面访问到 2.他需要用到this访问成员变量是形参this指针只能在函数内部使用void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;};
}namespace key_value
{templateclass K,class Vstruct BSTreeNode{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _value;BSTreeNode(const K key,const V value):_left(nullptr), _right(nullptr), _key(key),_value(value){}};templateclass K,class Vclass BSTree{typedef BSTreeNodeK,V Node;public:/*BSTree():_root(nullptr){}*/BSTree() default; //指定强制生成默认构造BSTree(const BSTreeK,V t){_root Copy(t._root);}BSTreeK,V operator(BSTreeK,V t){swap(_root, t._root);return *this;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}~BSTree(){Destroy(_root);_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}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;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}bool FinR(const K key){return _FindR(_root, key);}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool InsertR(const K key){return _InsertR(_root, key);}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;//开始准备删除if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* maxleft root-_left;while (maxleft-_right){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);return _EraseR(root-_left, key);//return _EraseR(maxleft, key); //不能使用maxleft不然引用不起作用}delete del;return true;}}bool EraseR(const K key){return _EraseR(_root, key);}bool Erase(const K key){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{//删除//1.左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//找右树最小节点替代也可以是左树最大节点替代Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}//protected://void _InOrder(Node* root_root) 1.缺省值必须是全局变量或者是常量要在类里面访问到 2.他需要用到this访问成员变量是形参this指针只能在函数内部使用void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
}8.1 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includestring
using namespace std;#include BSTree.hvoid TestBSTree()
{int a[] { 8,3,1,10,6,4,7,14,13 };key::BSTreeint t1;for (auto e : a){//t1.Erase(e);t1.Insert(e);}//t1.InOrder(t1.GetRoot());t1.InOrder();t1.Erase(4);t1.InOrder();t1.Erase(14);t1.InOrder();t1.Erase(3);t1.InOrder();t1.Erase(8);t1.InOrder();for (auto e : a){t1.Erase(e);}t1.InOrder();}void TestBSTree1()
{int a[] { 8,3,1,10,6,4,7,14,13 };key::BSTreeint t1;for (auto e : a){t1.InsertR(e);}t1.InOrder();t1.EraseR(4);t1.InOrder();t1.EraseR(14);t1.InOrder();t1.EraseR(3);t1.InOrder();t1.EraseR(8);t1.InOrder();key::BSTreeint t2(t1);t2.InOrder();}void TestBSTree2()
{key_value::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(left, 左边);dict.Insert(right, 右边);dict.Insert(string, 字符串);dict.Insert(insert, 插入);dict.Insert(erase, 删除);string str;while (cin str){auto ret dict.Find(str);if (ret){cout : ret-_value endl;}else{cout 无此单词 endl;}}}void TestBSTree3()
{// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };key_value::BSTreestring, int countTree;for (auto str : arr){//key_value::BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}int main()
{//TestBSTree();TestBSTree1();//TestBSTree2();//TestBSTree3();return 0;
}
