目录1 二叉搜索树的概念2 二叉搜索树的插入3 二叉搜索树的查找4 二叉搜索树的删除5 二叉搜索树的更新6 二叉搜索树的效率7 二叉搜索树的代码实现1 二叉搜索树的概念二叉搜索树又叫做二叉排序树缩写为BST Binary Search Tree二叉搜索树可以是一颗空树也可以是一颗具有以下特性的二叉树如果它的左子树不为空左子树中结点的值要小于根节点的值如果它的右子树不为空右子树中结点的值要大于根节点的值左右子树又分别是一棵 BST即左小于根小于右左右又是BST2 二叉搜索树的插入二叉搜索树在进行插入时要分情况讨论如果是空树插入一个结点后它变成根节点如果不是空树使用要插入的值和每个结点进行比对小于时则向左子树移动大于时则向右子树移动等于时向左向右都可以直到找到空结点才进行插入和链接。如果等于时直接返回不进行插入就可以进行去重3 二叉搜索树的查找二叉搜索树在查找时与插入类似也是拿要查找的值和结点中保存的值作对比如果小于则向左子树移动如果大于则向右子树移动。如果到空结点则说明要查找的值不在二叉搜索树内查找结束如果二叉搜索树中有相同的值查找到中序的第一个值即可返回如果二叉搜索树中没有相同的值查找到匹配的值即可返回查找成功的情况查找失败的情况4 二叉搜索树的删除二叉搜索树的删除要先查找要删除的结点查找不到直接返回 false找到了再分情况讨论要删除的结点是叶子结点直接删除并将父亲结点对应的指针置为空即可要删除的结点有左子树没有右子树那么就需要将它的左子树链接至它的父亲结点上再删除该结点要删除的结点有右子树没有左子树那么就需要将它的右子树链接至它的父亲结点上再删除该节点要删除的结点既有左子树又有右子树可以选择用左子树中最大的值替换掉要删除结点的值转而去删除最大的值也可以选择用右子树中最小的值替换掉要删除结点的值转而去删除最小的值左子树中最大的值一定在最右下角右子树中最小的值一定在最左下角删除的是叶子结点删除的结点有左孩子删除的结点有右孩子删除的结点既有左孩子又有右孩子使用左子树中最大的值进行替换转而删除左子树中最大的值使用右子树中最小的值进行替换转而删除右子树中最大的值5 二叉搜索树的更新二叉搜索树不存在更新操作因为一旦将二叉搜索树结点的值更改那么整个二叉搜索树的结构就可能会混乱不符合左小于根小于右的规则6 二叉搜索树的效率二叉搜索树中不管是新增删除还是查找都需要依照左小于根小于右来查找结点所以查找占了二叉搜索树操作的大部分时间对于查找要分两种情况说明最好情况如果当前的二叉搜索树是一颗完全二叉树结点的个数是 N那么树高就是 log2N查找的时间复杂度就是O(log2N)最坏情况如果当前的二叉搜索树是一颗单支树结点的个数是 N那么树高就是 N查找的时间复杂度就是O(N)7 二叉搜索树的代码实现//BST结点templateclassKclassBSTNode{public:BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}K _key;BSTNodeK*_left;BSTNodeK*_right;};//BST本体templateclassKclassBSTree{//typedef BSTNodeK Node;usingNodeBSTNodeK;public:BSTree()default;BSTree(constBSTreet){_rootcopy(t._root);}BSTreeoperator(constBSTree tmp){swap(_root,tmp._root);return*this;}~BSTree(){//后序遍历析构destroy(_root);_rootnullptr;}//插入boolinsert(constKkey){if(_rootnullptr){_rootnewNode(key);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(key);if(keyparent-_key){parent-_rightcur;}elseif(keyparent-_key){parent-_leftcur;}returntrue;}//查找boolfind(constKkey){if(_rootnullptr)returnfalse;Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;}}returnfalse;}//删除boolerase(constKkey){if(_rootnullptr)returnfalse;Node*parentnullptr;Node*cur_root;while(cur){//查找if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else//查找成功进行删除{if(cur-_leftcur-_rightnullptr)//只有左孩子时{if(cur_root)//删除的是根节点{_rootcur-_left;//将左子树的根节点视为新的根节点}else//删除的不是根节点{if(curparent-_left)//位于父结点左侧{parent-_leftcur-_left;//将左孩子连接至父结点左侧}elseif(curparent-_right)//位于父结点右侧{parent-_rightcur-_left;//将左孩子连接至父结点右侧}}deletecur;}elseif(cur-_leftnullptrcur-_right)//只有右孩子时{if(cur_root)//删除的是根节点{_rootcur-_right;//将右子树的根节点视为新的根节点}else//删除的不是根节点{if(curparent-_left){parent-_leftcur-_right;}elseif(curparent-_right){parent-_rightcur-_right;}}deletecur;}else//有左右孩子时{Node*rightMinParentcur;Node*rightMincur-_right;//查找右子树中最小的结点while(rightMin-_left){rightMinParentrightMin;rightMinrightMin-_left;}//更改待删除结点的值cur-_keyrightMin-_key;//将右子树中最小的结点的孩子接到父亲上再进行删除if(rightMinParent-_leftrightMin){rightMinParent-_leftrightMin-_right;}elseif(rightMinParent-_rightrightMin){rightMinParent-_rightrightMin-_right;}deleterightMin;}returntrue;}}returnfalse;}//中序遍历voidinOrder(){_InOrder(_root);coutendl;}private:void_InOrder(Node*_root){if(_rootnullptr)return;_InOrder(_root-_left);cout_root-_key ;_InOrder(_root-_right);}voiddestroy(Node*_root){if(_rootnullptr)return;destroy(_root-_left);destroy(_root-_right);delete_root;}Node*copy(Node*_root){if(_rootnullptr)returnnullptr;Node*newRootnewNode(_root-_key);newRoot-_leftcopy(_root-_left);newRoot-_rightcopy(_root-_right);returnnewRoot;}Node*_rootnullptr;//根结点};