1.概念二叉搜索树又称二叉排序树或者二叉查找树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树。2.特点1. 有序性这是最核心的特点。对BST进行中序遍历左-根-右能得到一个严格递增无重复值时的有序序列如同按顺序翻阅一本排好序的字典。2. 查找高效类似“二分查找”逻辑每次比较可排除一半子树。若树平衡查找、插入、删除操作时间复杂度为O(log n)若失衡如退化为链表则降为O(n)。3. 结构约束每个节点的左子树仅存储更小的值右子树仅存储更大的值不存在值相等的节点通常定义也有允许重复值的变体需额外约定存储位置。3.二叉树的操作3.1 二叉树的查找1、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。2、最多查找高度次走到到空还没找到这个值不存在。3.2二叉树的插入1. 树为空则直接新增节点赋值给root指针。2. 树不空按二叉搜索树性质查找插入位置插入新节点。3.3 二叉树的删除首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况1. 要删除的结点无孩子结点2. 要删除的结点只有左孩子结点3. 要删除的结点只有右孩子结点4. 要删除的结点有左、右孩子结点看起来有待删除节点有4中情况实际情况1可以与情况2或者3合并起来因此真正的删除过程如下情况2删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除情况3删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除情况4在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除4.二叉搜索树的模拟实现4.1 节点的实现struct BSTreeNode { BSTreeNodeK* _left;//左节点指针 BSTreeNodeK* _right;//右节点指针 K _key; BSTreeNode(const K key) :_left(nullptr) , _right(nullptr) , _key(key) {} };4.2 查找的实现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; }查找逻辑是从根节点开始查找。如果查找值比当前值大时往右走查找值比当前值小时往左走否则就是相等即找到了。4.3 插入的实现bool insert(const K key) { if (_root nullptr) { _root new node(key); return true; } node* partent nullptr; node* cur _root; while (cur) { if (cur-_key key) { partent cur; cur cur-_right; } else if (cur-_key key) { partent cur; cur cur-_left; } else { return false;//不允许重复 } } cur new node(key); if (partent-_key key) { partent-_right cur; } else if (partent-_key key) { partent-_left cur; } return true; }如果是空树就直接创建一个新的节点不是的话就从根节点开始比较小就往左走大就往右走同时要记录父节点的指针找到合适的位置创建节点建立链接。4.4 删除的实现bool erase(const K key) { node* partent nullptr; node* cur _root; while (cur) { if (cur-_key key) { partent cur; cur cur-_right; } else if (cur-_key key) { partent cur; cur cur-_left; } else//找到了 { if (cur-_left nullptr)//左为空 { if (cur _root) { _root cur-_right; } else { if (partent-_right cur) { partent-_right cur-_right; } else { partent-_left cur-_right; } } } else if (cur-_right nullptr)//右为空 { if (cur _root) { _root cur-_left; } else { if (partent-_right cur) { partent-_right cur-_left; } else { partent-_left cur-_left; } } } else//左右都不为空 { node* partent cur;//找替代节点 node* leftmax cur-_left; while (leftmax-_right)//找最右节点 { partent leftmax; leftmax leftmax-_right; } swap(leftmax-_key, cur-_key); if (partent-_left leftmax) { partent-_left leftmax-_left; } else { partent-_right leftmax-_left; } cur leftmax; } delete cur; return true; } } return false; }删除的比较复杂一段一段拿出来分析分析要删除的节点左节点存在右节点为空的情况红色的节点表示要删除的节点。node* partent nullptr; node* cur _root; while (cur) { if (cur-_key key) { partent cur; cur cur-_right; } else if (cur-_key key) { partent cur; cur cur-_left; } else//找到了 { if (cur-_left nullptr)//左为空 { if (cur _root) { _root cur-_right; } else { if (partent-_right cur) { partent-_right cur-_right; } else { partent-_left cur-_right; } } } else if (cur-_right nullptr)//右为空 { if (cur _root) { _root cur-_left; } else { if (partent-_right cur) { partent-_right cur-_left; } else { partent-_left cur-_left; } } }这时候cur已经指向了要删除的节点如果被删除的节点左边的节点为空的话只需要把它的判断它在父节点的左边还是右边在左边。让父节点的左指针指向它的右节点在右边就让父节点的右指针指向它的右节点。ps:要注意如果要删除的节点是根节点那么父节点就是空节点调用会报错所以要先判断是否为根节点。分析都不为空的情况else//左右都不为空 { node* partent cur;//找替代节点 node* leftmax cur-_left; while (leftmax-_right)//找最右节点 { partent leftmax; leftmax leftmax-_right; } swap(leftmax-_key, cur-_key); if (partent-_left leftmax) { partent-_left leftmax-_left; } else { partent-_right leftmax-_left; } cur leftmax; }首先要找代替节点可以找左子树的最右节点或者右子树的最左节点代码中找的是左子树的最右节点找到替代节点后交换两个节点的值这个时候不能直观的认为替换的节点虽然是左子树的最右节点但是并不一定它一定在父节点的右边还要判断并且父节点不能一上来就置为空如果是上图的情况就会出问题。4.5 二叉搜索树的遍历void _inorder(node* root) { if (root nullptr) { return; } _inorder(root-_left); cout root-_key ; _inorder(root-_right); }这里实现的是中序遍历。5.二叉搜索树的模拟实现(递归版)5.1 查找的实现bool _findr(node* root, const K key) { if (root nullptr) return false; if (root-_key key) { return _findr(root-_left,key); } else if (root-_key key) { return _findr(root-_right,key); } else { return true; } }递归查找逻辑是如果当前根的值小于目标值递归至右树查找如果当前根的值大于目标值递归至左树查找否则就是找到了返回true。5.2 插入的实现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; }如果是空树就直接创建一个新的节点不是的话就从根节点开始比较小就递归到左数去比较大就递归到右数去比较找到合适的位置创建节点建立链接如果遇到一样的就返回错误。4.4 删除的实现bool _eraser(node* root, const K key) { if (root nullptr) return false; if (root-_key key) { return _eraser(root-_left,key); } else if (root-_key key) { return _eraser(root-_right,key); } else { node* del root; if (root-_left nullptr) { root root-_right; } else if (root-_right nullptr) { root root-_left; } else { node* leftmax root-_left; while (leftmax-right) { leftmax leftmax-_right; } swap(root-_key, leftmax-_key); return _eraser(root-_left, key); } delete del; return true; } }分析要删除的节点左右节点为空的情况使用指针引用在递归中root存储的左或右指针的引用当找到要删除的值时直接改变指针的指向即可。当递归到root为要删除的节点时因为我们使用了指针引用所以这个时候root是节点3的右指针引用我们直接改变节点3的右指针的指向指向为4即可。分析都不为空的情况找到左子树的最右节点交换两个数的值在递归中去删除因为交换了之后左子树的最右节点的位置的右一定是空的。4.5 析构函数void destory(node* root) { if (root nullptr) return; destory(root-_left); destory(root-_right); delete root; root nullptr; }由于二叉搜索树的节点是通过new创建在堆上的所以在销毁二叉搜索树时需要递归地释放每个节点的内存。这里采用后序遍历的方式先释放左右子树再释放根节点。4.6 拷贝构造和赋值重载node* copy(node* root) { if (root nullptr) return nullptr; node*copyroot new node(root-_key, root-_value); copyroot-_leftcopy(root-_left); copyroot-_rightcopy(root-_right); return copyroot; } BSTreeK operator(BSTreeK t) { swap(_root, t._root); return *this; }拷贝构造运行前序遍历先拷贝根节点再拷贝左右节点赋值重载直接使用swap函数。6.模拟实现的两个版本的完整代码templateclass K struct BSTreeNode { BSTreeNodeK* _left;//左节点指针 BSTreeNodeK* _right;//右节点指针 K _key; BSTreeNode(const K key) :_left(nullptr) , _right(nullptr) , _key(key) {} }; templateclass K class BSTree { typedef BSTreeNodeK node; public: BSTree() :_root(nullptr) {} BSTree(const BSTreeK t) { _root copy(t._root); } BSTreeK operator(BSTreeK t) { swap(_root, t._root); return *this; } ~BSTree() { destory(_root); } 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 insert(const K key) { if (_root nullptr) { _root new node(key); return true; } node* partent nullptr; node* cur _root; while (cur) { if (cur-_key key) { partent cur; cur cur-_right; } else if (cur-_key key) { partent cur; cur cur-_left; } else { return false;//不允许重复 } } cur new node(key); if (partent-_key key) { partent-_right cur; } else if (partent-_key key) { partent-_left cur; } return true; } bool erase(const K key) { node* partent nullptr; node* cur _root; while (cur) { if (cur-_key key) { partent cur; cur cur-_right; } else if (cur-_key key) { partent cur; cur cur-_left; } else//找到了 { if (cur-_left nullptr)//左为空 { if (cur _root) { _root cur-_right; } else { if (partent-_right cur) { partent-_right cur-_right; } else { partent-_left cur-_right; } } } else if (cur-_right nullptr)//右为空 { if (cur _root) { _root cur-_left; } else { if (partent-_right cur) { partent-_right cur-_left; } else { partent-_left cur-_left; } } } else//左右都不为空 { node* partent cur;//找替代节点 node* leftmax cur-_left; while (leftmax-_right)//找最右节点 { partent leftmax; leftmax leftmax-_right; } swap(leftmax-_key, cur-_key); if (partent-_left leftmax) { partent-_left leftmax-_left; } else { partent-_right leftmax-_left; } cur leftmax; } delete cur; return true; } } return false; } void inorder() { _inorder(_root); } void findr(const K key) { return _findr(_root, key); } void insertr(const K key) { return _insertr(_root, key); } void eraser(const K key) { return _eraser(_root, key); } private: node* copy(node* root) { if (root nullptr) return nullptr; node* copyroot new node(root-_key); copyroot-_leftcopy(root-_left); copyroot-_rightcopy(root-_right); return copyroot; } void destory(node* root) { if (root nullptr) return; destory(root-_left); destory(root-_right); delete root; root nullptr; } bool _findr(node* root, const K key) { if (root nullptr) return false; if (root-_key key) { return _findr(root-_left,key); } else if (root-_key key) { return _findr(root-_right,key); } else { return true; } } 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 _eraser(node* root, const K key) { if (root nullptr) return false; if (root-_key key) { return _eraser(root-_left,key); } else if (root-_key key) { return _eraser(root-_right,key); } else { node* del root; if (root-_left nullptr) { root root-_right; } else if (root-_right nullptr) { root root-_left; } else { node* leftmax root-_left; while (leftmax-right) { leftmax leftmax-_right; } swap(root-_key, leftmax-_key); return _eraser(root-_left, key); } delete del; return true; } } void _inorder(node* root) { if (root nullptr) { return; } _inorder(root-_left); cout root-_key ; _inorder(root-_right); } node* _root; };7.二叉树的应用场景1.key模型用“唯一标识”锁定目标一个key对应一个确定的实体/数据身份证号 → 个人信息图书ISBN码 → 书籍详情。2.key_value模型用“键值对”映射现实关系学生学号key→ 成绩value商品条形码key→ 价格value。7.1 二叉搜索树小结插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)效率为logN。最差情况下二叉搜索树退化为单支树(或者类似单支)效率为N。