二叉搜索树文章目录二叉搜索树[toc]key 版1.概念总览2.性能3.头文件4.节点结构BSTNode5.二叉搜索树结构BSTreeusing6.插入Insert7.中序遍历InOrder8.查找Find9.删除Erase分情况找到了后解决key_value 版10.节点结构BSTNodeK, V11.插入Insert12.中序遍历InOrder13.查找Find14.删除Erase测试key 版1.概念总览二叉树每个根只有一个或两个孩子二叉搜索树一种二叉树左孩子根右孩子根map、set、multimap、multiset的底层容器都是二叉搜索树后两个允许重复前两个不允许2.性能最优log₂N最差N相当于单支3.头文件#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#includeiostreamusingnamespacestd;4.节点结构BSTNode存放值K _key;左右节点的指针_left_right初始化列表节点中存放的内容没有用private因为后面Insert中要用templateclassKclassBSTNode{public:BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}/// summary/// 这里我添加了private但是添加了之后后面就访问不了了所以不能添加/// /summaryK _key;BSTNodeK*_left;BSTNodeK*_right;};5.二叉搜索树结构BSTree在 二叉搜索树 这个类中为了方便 把BSTNode这个节点结构 重命名了一下using Node BSTNodeK;using相当于typedef二者的用法给A重命名为B typedef A B using B A ;templateclassKclassBSTree{public:usingNodeBSTNodeK;boolInsert(constKkey);voidInOrder();boolFind(constKkey);boolErase(constKkey);private:void_InOrder(Node*node);Node*_rootnullptr;};6.插入Insert空树直接创建节点非空一路上要记着父节点先找空位key小往左走key大往右走一样大return false这时候cur在空位parent无法判断cur是左孩子还是右孩子所以要进行左右分类看if (parent-_key key)……else……然后插入keyreturn trueboolInsert(constKkey){if(_rootnullptr)///这地方我犯了个错写成了一个等于号{_rootnewNode(key);returntrue;///这个点我也没注意}else{Node*cur_root;Node*parentnullptr;while(cur){if(keycur-_key){parentcur;curcur-_left;}elseif(keycur-_key){parentcur;curcur-_right;}else{returnfalse;}}//if (parent-_left cur) // 注意这是赋值 不是比较 ///if (parent-_left cur)// ❌ 逻辑错误,退出 while 循环时 cur 是 nullptr, 那如果左右都是空要插的是右边这时就不对if(parent-_keykey){/*cur new Node(key); parent-_left cur;*////更简约版parent-_leftnewNode(key);}else{/*cur new Node(key); parent-_right cur;*////更简约版parent-_rightnewNode(key);}returntrue;}}7.中序遍历InOrder遍历的时候要从根节点开始就要访问_root可是BSTree里面 的_root是private的不能访问所以public提供无参的InOrder()对外接口调用private隐藏带参的_InOrder(Node*)实现voidInOrder(){_InOrder(_root);///(Node * root); // 这是声明不是调用coutendl;}void_InOrder(Node*node){//if (node-_left)// 如果 node 是 nullptr这里直接崩了//{// _InOrder(node-_left);//}//cout node-_key ;//if (node-_right)//{// _InOrder(node-_right);//}if(nodenullptr)return;_InOrder(node-_left);coutnode-_key ;// cour 拼写错误_InOrder(node-_right);}8.查找Find和插入差不多就是向下找并且还不需要parent了找到返回就行boolFind(constKkey){///parent 是没有用的//if (_root nullptr)// return false;//else//{// Node* cur _root;// Node* parent nullptr;// while (cur)// {// if (cur-_key key)// return true;// else if (key cur-_key)// {// parent cur;// cur cur-_left;// }// else// {// parent cur;// cur cur-_right;// }// }// return false;//}Node*cur_root;while(cur){if(keycur-_key)returntrue;elseif(keycur-_key){curcur-_left;}else{curcur-_right;}}returnfalse;}9.删除Erase分情况无节点return false;有节点先找要删除的节点——找到没找到还 要判断如果找到了没有左孩子的情况没有右孩子的情况两个孩子都有的情况找到了后解决只有左/右 孩子先判断cur是parent的左还是右把另一个孩子直接替换到cur的位置两个孩子都有找到cur要删除节点的右子树 的最左侧的节点cur要删除节点50的右子树 70 没有左孩子——直接用70和他后面一整串替代掉5050 的右子树70 有左孩子——不断找左孩子直到找到55把55 放到50的位置然后将原来55右的一串 接到60左边boolErase(constKkey){if(_rootnullptr)returnfalse;else{Node*cur_root;Node*parentnullptr;while(cur){if(keycur-_key){parentcur;curcur-_left;}elseif(keycur-_key){parentcur;curcur-_right;}elsebreak;}if(curnullptr)returnfalse;else///找到了{if(cur-_leftnullptr)///左为空{if(cur_root)////////////////////////////{_root_root-_right;}else{if(parent-_leftcur)///cur左为空 cur是parent的左parent-_leftcur-_right;else///cur左为空 cur是parent的右parent-_rightcur-_right;}}elseif(cur-_rightnullptr)///右为空{if(cur_root)////////////////////////////{_root_root-_left;}else{if(curparent-_left)parent-_leftcur-_left;elseparent-_rightcur-_left;}}else///左右都不为空{//找到右子树的最小值最左边///要删除节点的 右节点 没有左节点if(cur-_right-_leftnullptr){Node*to_deletecur-_right;cur-_keycur-_right-_key;cur-_rightcur-_right-_right;deleteto_delete;}///要删除节点的 右节点 还有左节点else{Node*changeparentcur;Node*changecurcur-_right;while(changecur-_left){changeparentchangecur;changecurchangecur-_left;}cur-_keychangecur-_key;changeparent-_leftchangecur-_right;///如果没有这一条就把 changecur 的右子树整棵丢掉了deletechangecur;//changeparent-_left nullptr;}}returntrue;}}}key_value 版10.节点结构BSTNodeK, VtemplateclassK,classVclassBSTNode{public:BSTNode(constKkey,constVvalue):_key(key),_value(value),_left(nullptr),_right(nullptr){}/// summary/// 这里我添加了private但是添加了之后后面就访问不了了所以不能添加/// /summaryK _key;V _value;BSTNodeK,V*_left;BSTNodeK,V*_right;};usingNodeBSTNodeK,V;Node*_rootnullptr;11.插入Insert插入的内容多了一类valueInsert(const K key, const V value)创建根节点的时候默认构造也变了_root new Node(key, value);创建新节点的时 也变了new Node(key, value);boolInsert(constKkey,constVvalue){if(_rootnullptr)///这地方我犯了个错写成了一个等于号{_rootnewNode(key,value);returntrue;///这个点我也没注意}else{Node*cur_root;Node*parentnullptr;while(cur){if(keycur-_key){parentcur;curcur-_left;}elseif(keycur-_key){parentcur;curcur-_right;}else{returnfalse;}}//if (parent-_left cur) // 注意这是赋值 不是比较 ///if (parent-_left cur)// ❌ 逻辑错误,退出 while 循环时 cur 是 nullptr, 那如果左右都是空要插的是右边这时就不对if(parent-_keykey){/*cur new Node(key); parent-_left cur;*////更简约版parent-_leftnewNode(key,value);}else{/*cur new Node(key); parent-_right cur;*////更简约版parent-_rightnewNode(key,value);}returntrue;}}12.中序遍历InOrder输出变成了两个值key和valuecout node-_key : node-_value ;voidInOrder(){_InOrder(_root);///(Node * root); // 这是声明不是调用coutendl;}void_InOrder(Node*node){//if (node-_left)// 如果 node 是 nullptr这里直接崩了//{// _InOrder(node-_left);//}//cout node-_key ;//if (node-_right)//{// _InOrder(node-_right);//}if(nodenullptr)return;_InOrder(node-_left);coutnode-_key:node-_value ;// cour 拼写错误_InOrder(node-_right);}13.查找Find查找没有变化14.删除Erase待删除节点左右都有节点的时候要进行替换把这个待删除的节点 的_key和_value都改boolErase(constKkey){if(_rootnullptr)returnfalse;else{Node*cur_root;Node*parentnullptr;while(cur){if(keycur-_key){parentcur;curcur-_left;}elseif(keycur-_key){parentcur;curcur-_right;}elsebreak;}if(curnullptr)returnfalse;else///找到了{if(cur-_leftnullptr)///左为空{if(cur_root)////////////////////////////{_root_root-_right;}else{if(parent-_leftcur)///cur左为空 cur是parent的左parent-_leftcur-_right;else///cur左为空 cur是parent的右parent-_rightcur-_right;}}elseif(cur-_rightnullptr)///右为空{if(cur_root)////////////////////////////{_root_root-_left;}else{if(curparent-_left)parent-_leftcur-_left;elseparent-_rightcur-_left;}}else///左右都不为空{//找到右子树的最小值最左边///要删除节点的 右节点 没有左节点if(cur-_right-_leftnullptr){Node*to_deletecur-_right;cur-_keycur-_right-_key;cur-_valuecur-_right-_value;cur-_rightcur-_right-_right;deleteto_delete;}///要删除节点的 右节点 还有左节点else{Node*changeparentcur;Node*changecurcur-_right;while(changecur-_left){changeparentchangecur;changecurchangecur-_left;}cur-_keychangecur-_key;cur-_valuechangecur-_value;changeparent-_leftchangecur-_right;///如果没有这一条就把 changecur 的右子树整棵丢掉了deletechangecur;//changeparent-_left nullptr;}}returntrue;}}}测试#define_CRT_SECURE_NO_WARNINGS1#includeBinarySearchTree.hintmain(){//key::BSTreeint t; // 此时先不用命名空间直接 BSTreeint t;//int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };//// TODO: 范围 for 逐个 Insert//// TODO: InOrder 打印应为有序序列inta[]{8,3,1,10,1,6,4,7,14,13};// 4. × 要改BSTree 现在被放进了 namespace key直接写 BSTree 编译找不到它// 4. √ 改成key::BSTreeint t;BSTreeintt;for(inti0;isizeof(a)/sizeof(int);i){t.Insert(a[i]);}t.InOrder();t.Erase(7);t.InOrder();return0;}