企业官网建设流程全解析

二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：

●若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值

●若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值

●它的左右子树也分别为二叉搜索树

●二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，当我们使用map/set/multimap/multiset系列容器时，它们的底层就是二叉搜索树，其中map/set不支持插入相等的值，multimap/multiset支持插入相等值

因为这个“左小右大”的规则，二叉搜索树拥有了非常高效的查找能力。同时，对它进行中序遍历，得到的结果就是从小到大有序的。这一点在我们后面的代码中会直接体现出来。

二叉搜索树的性能特征

任何数据结构的操作效率都和它的形状强相关。

最优情况：树长得像一棵“完全二叉树”（或者说非常平衡），树的高度 h 约等于 log₂N。此时插入、删除、查找的时间复杂度都是 O(log N)。
最差情况：插入的序列本身是有序的（一直往右或一直往左），树就退化成了一条“单链表”，高度等于 N。此时复杂度退化为 O(N)。

因此，综合而言二叉搜索树增删查改的时间复杂度是O(N)。这显然不能满足工程要求，所以后来才衍生出了 AVL 树和红黑树这样的“平衡二叉搜索树”。

你可能会想：二分查找也是 O(log N)，为什么还要搞这么复杂的树结构？
二分查找虽然查找快，但有两个致命缺陷：

数据必须存储在支持随机访问的结构（如数组）中，并且要提前排好序；
插入和删除数据时，数组需要挪动大量元素，代价很高。

平衡二叉搜索树则解决了“动态数据”的高效增删查问题。
我们下面的代码实现的就是普通的二叉搜索树，虽然它可能不平衡，但其思想是后续一切平衡树的根基。

二叉搜索树的实现

节点结构体

template<classK>structBSTNode{K _key;BSTNode<K>*_left;BSTNode<K>*_right;BSTNode(constK&key):_key(key),_left(nullptr),_right(nullptr){}};

节点包含三个成员：_key、左孩子指针 _left、右孩子指针 _right。
构造函数用初始化列表把所有成员初始化好，左右指针初始为空。
这里使用了模板 template，让节点可以存任意类型的 key（int、string 等）。
BSTNode（节点）：不需要拷贝构造。节点只存储数据和子节点指针，不负责子节点内存释放，编译器默认拷贝即可。

二叉搜索树类的基本框架

template<classK>classBSTree{// 类型别名：方便在类中使用//这里用到了 using Node = BSTNode<K>;，等价于 typedef BSTNode<K> Node;usingNode=BSTNode<K>;public:// 默认构造：编译器生成即可BSTree()=default;// 拷贝构造BSTree(constBSTree&t){_root=Copy(t._root);}// 赋值运算符重载BSTree&operator=(BSTree tmp){swap(_root,tmp._root);return*this;}// 析构函数~BSTree(){Destroy(_root);_root=nullptr;}// 核心操作：增、查、删、遍历boolInsert(constK&key);boolfind(constK&key);boolErase(constK&key);voidInorder();private:// 内部递归辅助函数void_Inorder(Node*root);//私有成员函数，BSTree类里面template<classK>BSTNode<K>*Copy(BSTNode<K>*root){//递归终止条件：空节点直接返回nullptrif(root==nullptr){returnnullptr;}//复制当前节点：new全新节点，不是复用旧节点！BSTNode<K>*newNode=newBSTNode<K>(root->_key);//递归拷贝左子树，接到新节点左指针newNode->_left=Copy(root->_left);//递归拷贝右子树，接到新节点右指针newNode->_right=Copy(root->_right);returnnewNode;}template<classK>voidDestroy(BSTNode<K>*&root){if(root==nullptr)return;//后序遍历：先销毁左、再销毁右，最后销毁自己Destroy(root->_left);Destroy(root->_right);deleteroot;root=nullptr;}};

BSTree（树管理类）：必须实现拷贝构造，做深拷贝。因为树拥有全部节点，析构要销毁全部堆节点；拷贝时递归Copy，每一个节点都 new 出新对象，得到完全独立的新树。
深拷贝发生在树这一层，递归遍历所有节点逐个新建，而不是单个节点层面。

插入操作 (Insert)(写在类里面)

思路：

若树为空，直接让根指向新节点。
若树不空，从根开始比较： 插入值 大于 当前节点 → 往右走；
插入值 小于 当前节点 → 往左走；
若相等-> 说明节点已存在，插入失败（我们实现的代码中不允许重复 key）。 走到某个位置，发现下一步是 nullptr，那里就是该插入的位置。
如果支持插入相等的值，插入的值和当前结点的值相等可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
出于维护树结构需要，我们在查找过程中要留下“父节点”的痕迹，这样才能把新节点挂到父节点的左/右指针.

boolInsert(constK&key){// 1. 空树：直接成为根if(_root==nullptr){_root=newNode(key);returntrue;}Node*parent=nullptr;// 记录当前节点的父亲Node*cur=_root;// 从根开始查找// 2. 找到插入位置while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;// 去右边找}elseif(cur->_key>key){parent=cur;cur=cur->_left;// 去左边找}else{returnfalse;// 相等，不允许重复，插入失败}}// 3. 出来时 cur 为空，parent 是待插入位置的父节点cur=newNode(key);if(parent->_key<key){parent->_right=cur;// 比父亲大，挂右边}else{parent->_left=cur;// 比父亲小，挂左边}returntrue;}

注
parent 必须记录，不然新节点不知道挂到哪个节点下。
判断挂在左还是右，取决于新 key 与 parent->_key 的大小关系。由于我们确认过 key 不等于 parent->_key（否则早已返回 false），所以只可能是大于或小于。

查找操作 (find)

查找逻辑和插入的“定位”过程几乎一模一样：从根开始，比当前节点大就往右，小就往左，等于就找到了。走到空还没找到，说明不存在。
如果支持插入相等的值，意味着有多个相等的值存在，一般要求查找 中序 的第一个相等的值。如下图，查找3，要找到1的右孩子的那个3返回。

boolfind(constK&key){Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{returntrue;// 找到了}}returnfalse;// cur 为空，没找到}

查找是不修改树结构的，所以不需要记录父节点，只用跟着指针一路向下即可。时间复杂度为 O(高)

删除操作 (Erase) —— 最复杂的部分

删除操作是二叉搜索树里逻辑最繁重的一环。先整体梳理步骤：

1.先查找要删除的节点 cur，同时记录它的父亲 parent。
2.若没找到，直接返回 false。
3.若找到了，分三种大情况处理（其实可以归并为四种，但代码实现时通常合并前两种）：
情况分析
假设待删节点为 N（即代码里的 cur）：
情况1：N 是叶子节点（左右孩子全为空）
直接把父节点指向它的指针置空，然后 delete N。
情况2：N 只有一个孩子
若 N 只有右孩子：让 N 的父节点原来指向 N 的指针改为指向 N 的右孩子，delete N。
若 N 只有左孩子：让 N 的父节点原来指向 N 的指针改为指向 N 的左孩子，delete N。
代码实现时我们把情况一和情况二进行了合并：


情况3：N 有两个孩子
这是最棘手的情况。我们不能直接删掉 N，因为它的两个孩子无处安放。
解决办法是替换法：
找一个“替身”节点 R，将它的值赋给 N（覆盖掉 N 的 key），然后改为删除 R。
R 必须满足：放在 N 的位置上，不会破坏二叉搜索树的性质。
通常选 N 的右子树中的最小节点（即右子树最左侧节点），或者 N 的左子树中的最大节点（即左子树最右侧节点）。本文代码的实现选择的是右子树最小节点。
这样选择的节点 R 必然最多只有一个孩子（右孩子），这样就可以转化为情况1或情况2来删除。


代码分布拆解

boolErase(constK&key){Node*parent=nullptr;Node*cur=_root;// 1. 查找待删节点while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else// 找到了，执行删除{// 进入具体删除逻辑...}}returnfalse;// 查找失败}

找到之后,进入删除逻辑
左孩子为空（包括了叶子节点和只有右孩子的情况）

if(cur->_left==nullptr){if(parent==nullptr)// 要删的是根节点，且根没有左子树{_root=cur->_right;}else{if(parent->_left==cur)// cur 是父亲的左孩子parent->_left=cur->_right;else// cur 是父亲的右孩子parent->_right=cur->_right;}deletecur;returntrue;}

当 cur->_left 为 nullptr 时，无论右孩子是否为空，处理方法都是把右孩子交给父亲。右孩子若为空，那父亲就指向了空，也就是删除叶子，逻辑完全正确。
特殊判断 parent == nullptr：当要删除的节点恰好是整棵树的根时，父亲不存在，只能直接修改 _root。
右孩子为空（对称情况）

elseif(cur->_right==nullptr){if(parent==nullptr){_root=cur->_left;}else{if(parent->_left==cur)parent->_left=cur->_left;elseparent->_right=cur->_left;}deletecur;returntrue;}

原理和上面一样，不再赘述。
注意这里用的是 else if，能够走到这里说明 cur->_left != nullptr，也就是该节点有左孩子但无右孩子。
左右孩子都不为空 —— 替换法

else{// 选右子树的最小节点作为替身Node*replaceParent=cur;// 注意：不能初始化为 nullptrNode*replace=cur->_right;// 右子树的根// 一路向左，找到最左节点while(replace->_left){replaceParent=replace;replace=replace->_left;}// 将替身节点的值赋给待删节点（覆盖）cur->_key=replace->_key;// 现在需要删除 replace 这个节点// replace 一定没有左孩子（因为已经是“最左”了）// 但它可能有右孩子，需要将 replace 的父亲指向它的右孩子if(replaceParent->_left==replace)replaceParent->_left=replace->_right;elsereplaceParent->_right=replace->_right;deletereplace;returntrue;}

几个关键问题：

为什么 replaceParent 不能初始化为 nullptr，而必须是 cur？
因为要找的是要删除节点的右子树的最小节点。如果右子树的根节点（指的是cur的右孩子节点） cur->_right 就没有左孩子，那么它本身就是最小节点，不会进入while循环。这时候 replaceParent 如果还是 nullptr，后面删除 replace 时会出现空指针访问。
用 cur 作为初始父节点，就涵盖了“最小节点就是右子树根”的情况，此时 while 循环不会进入，replaceParent 就是 cur，replace 是 cur->_right，后续的链接逻辑仍然正确.

为什么可以直接覆盖 cur->_key？
我们只是把“替身”的值拷贝给了待删节点，树的结构并没有被破坏。而替身节点本身的结构（位置、子树关系）将被移除。

删除替身节点时的父子关系处理
replace 必然没有左孩子，但可能有右子树。需要正确地将 replaceParent 的左或右指针连接到 replace->_right。

如果 replace 是 replaceParent 的左孩子，就接左指针；
否则（即 replace 就是 replaceParent 的右孩子，这种情况发生在最小节点就是 cur->_right 时），就接右指针。
这个判断非常关键，不能想当然地认为 replace 一定是左孩子。
至此，删除操作全部完成。

完整删除函数：

boolErase(constK&key){Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else// 找到了，开始删除{// 左孩子为空（包含左右都为空）if(cur->_left==nullptr){if(parent==nullptr)_root=cur->_right;else{if(parent->_left==cur)parent->_left=cur->_right;elseparent->_right=cur->_right;}deletecur;returntrue;}// 右孩子为空elseif(cur->_right==nullptr){if(parent==nullptr)_root=cur->_left;else{if(parent->_left==cur)parent->_left=cur->_left;elseparent->_right=cur->_left;}deletecur;returntrue;}// 有两个孩子：替换法else{Node*replaceParent=cur;Node*replace=cur->_right;while(replace->_left){replaceParent=replace;replace=replace->_left;}cur->_key=replace->_key;if(replaceParent->_left==replace)replaceParent->_left=replace->_right;elsereplaceParent->_right=replace->_right;deletereplace;returntrue;}}}returnfalse;// 没找到要删除的元素}

中序遍历与有序输出

二叉搜索树的中序遍历会得到一个升序序列，这时我们可以通过中序验证树结构的正确性。

voidInorder(){_Inorder(_root);cout<<endl;}private:void_Inorder(Node*root){if(root==nullptr){return;}_Inorder(root->_left);// 左cout<<root->_key<<" ";// 根_Inorder(root->_right);// 右}

为什么需要一个公有的 Inorder 和私有的 _Inorder 呢？因为二叉树的很多操作都需要传入节点指针 Node* root，但这个指针是树的私有成员 _root，用户无法直接获取。因此对外接口就是无参的，内部调用带参的私有函数，这种设计称为 “接口与实现分离”。

对外接口 Inorder() 封装了递归函数，外部不用关心根节点，只需调用。

二叉搜索树key和key/value的使用场景

key搜索场景：

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的只，搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词查找是否在二叉搜索树中，不在则波浪线标红提示。

intmain(){BSTree<int>t;inta[]={8,3,1,10,6,4,7,14,13};for(autoe:a){t.Insert(e);}t.Inorder();// 1 3 4 6 7 8 10 13 14// 依次删除所有节点，每删一个就遍历一次，观察是否仍然有序for(autoe:a){t.Erase(e);t.Inorder();}return0;}

key/value搜索场景：

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（节点）除了需要存储还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value，key/value的搜索场景实现的二叉搜索树支持修改，但是不支持修改key，修改key破环搜索树性质了，可以修改value。
比如：

电子词典：英文单词为 key，中文释义为 value。
车库计费：车牌号为 key，入场时间为 value。
单词统计：单词为 key，出现次数为 value。
在 KV 模型中，key 依然负责比较定位，value 只负责存储关联数据。增、删、查操作仍然按照 key 的大小规则进行。

KV 模型节点定义

template<classK,classV>structBSTNode{K _key;V _value;BSTNode<K,V>*_left;BSTNode<K,V>*_right;BSTNode(constK&key,constV&value):_key(key),_value(value),_left(nullptr),_right(nullptr){}};

多了一个模板参数 V，节点中多了 _value 成员。

KV 模型的 BSTree 类框架

这里的拷贝控制和我们上面实现的K模型相同：

template<classK,classV>classBSTree{usingNode=BSTNode<K,V>;public:BSTree()=default;// 默认构造BSTree(constBSTree&t)// 拷贝构造{_root=Copy(t._root);}BSTree&operator=(BSTree tmp)// 赋值运算符{swap(_root,tmp._root);return*this;}~BSTree()// 析构{Destroy(_root);_root=nullptr;}// ... 其他操作private:Node*_root=nullptr;};

KV 模型的 Insert、find、Erase 与 K 模型的逻辑相同，只是节点多了 value，查找返回的是节点指针（而不是 bool），以便获取 value。

Insert 示例

boolInsert(constK&key,constV&value){if(_root==nullptr){_root=newNode(key,value);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key)// 比当前 key 大，向右{parent=cur;cur=cur->_right;}elseif(cur->_key>key)// 小，向左{parent=cur;cur=cur->_left;}else{returnfalse;// 相等，不插入}}cur=newNode(key,value);if(parent->_key<key)parent->_right=cur;elseparent->_left=cur;returntrue;}

find 返回指针

Node*find(constK&key){Node*cur=_root;while(cur){if(cur->_key<key)cur=cur->_right;elseif(cur->_key>key)cur=cur->_left;elsereturncur;// 返回节点指针，可通过它修改 value}returnnullptr;}

删除逻辑 Erase 与 K 模型完全一致。

KV 模型应用场景

统计水果出现次数

intmain(){string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};key_value::BSTree<string,int>countTree;for(constauto&str:arr){autoret=countTree.find(str);if(ret==nullptr)// 第一次出现{countTree.Insert(str,1);}else// 已经存在，次数+1{ret->_value++;}}countTree.Inorder();// 输出：苹果:6 西瓜:3 香蕉:2// 测试拷贝功能key_value::BSTree<string,int>copy=countTree;copy.Inorder();return0;}

代码的工作原理：

每读到一个水果，先查找它是否已在树中。
如果不存在，插入 <水果, 1>。
如果存在，将对应节点的 _value 加一。

代码中的细节

尽管我们在上面逐段分析过，但想真正吃透，下面几点需要特别牢记：

删除有两个孩子节点的 replaceParent 初始化
Node* replaceParent = cur; 而不是 nullptr。这是防止 cur->_right 没有左子树时，循环完全不执行，replaceParent 若为 nullptr，后面判断 replaceParent->_left 就会挂掉 !!

删除 replace 节点时的链接判定

if(replaceParent->_left==replace)replaceParent->_left=replace->_right;elsereplaceParent->_right=replace->_right;

不能因为“反正是最左节点”就只写 _left，必须判断。

查找与插入中的 key 比较一致性
整个逻辑统一左小右大，比较时只用 _key 。KV 模型通过 key 查找并修改 value，绝不会修改 key，否则会破坏二叉搜索树结构。

递归中序遍历是理解 BST 的关键
二叉搜索树的中序序列一定是升序，这为我们验证程序正确性或调试提供了极大的便利。任何时候对树进行增删后，执行一次 Inorder，观察输出是否仍有序，基本就能判断逻辑是否出错