---

第十五章：二叉搜索树

一、课程前置：为什么普通二叉树没有实用价值

普通二叉树仅具备基础的树形结构，所有操作都依赖递归实现，逻辑复杂且无额外的业务价值：

1. 若仅用于存储数据，其存取效率和便捷性远不如链表，没有实际使用意义；
2. 普通二叉树仅作为数据结构的基础铺垫，只有在其基础上扩展规则、增加特性后，才能发挥实际价值；
3. 本节课的核心——二叉搜索树，就是普通二叉树最核心、最具实用价值的扩展形态。

二、二叉搜索树（BST）的核心定义与基础特性

2.1 核心定义

二叉搜索树（Binary Search Tree，简称BST，也叫二叉排序树），它或者是一棵空树，或者是在二叉树的基础上，叠加了一套严格的排序规则，树中每一个节点、每一棵子树都必须满足该规则：

1. 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；
2. 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值；
3. 它的左右子树也分别为二叉搜索树。

【命名提醒】老师特别强调：不要使用“搜索二叉树”作为全称，其拼音缩写容易被误解在偷偷骂人；统一使用“二叉搜索树”，标准缩写为BST，而非SBT。

2.2 关于相等值的补充规则

1. 二叉搜索树可以支持插入相等的值，也可以不支持，具体由使用场景定义；
2. 相等的值可以约定统一插入左子树或右子树，两种写法都符合BST规则，必须保持逻辑一致性，插入相等的值不要一会往右走、一会往左走；
3. 由于后续平衡操作的旋转会改变节点位置，即使约定了相等值的插入方向，最终相等值也可能出现在另一侧，因此无需纠结相等值的固定位置；
4. BST分为两类，对应C++ STL容器：
   • 不支持冗余（重复key）：key已存在时插入失败，对应map/set容器，工业界这种用法更多；
   • 支持冗余（重复key）：允许插入相同key，对应multimap/multiset容器。

2.3 两大核心特性

1. 天生适配搜索/查找场景
   无需像数组、链表那样暴力遍历全量数据，可通过节点大小关系快速缩小查找范围，查找效率远高于暴力遍历。
2. 中序遍历结果为升序序列
   中序遍历的规则是左子树 → 根节点 → 右子树，正好对应BST小 → 中 → 大的数值规则，因此中序遍历必然输出升序结果，这也是它被称为二叉排序树的原因。

   【核心结论】BST的中序遍历是最具价值的遍历方式，可通过中序结果是否升序，快速验证BST的结构是否正确。

三、二叉搜索树的核心操作：查找

3.1 传统暴力查找的缺陷

数组、链表的查找只能通过暴力遍历实现，时间复杂度为O(n)，查找效率完全取决于元素位置，运气好时一次找到，运气差时需要遍历全量数据。

3.2 BST的查找逻辑

BST的查找完全依托其核心排序规则，无需遍历全量数据，步骤如下：

1. 从根节点开始遍历；
2. 目标值 > 当前节点值：目标值只可能在右子树，跳转到右孩子继续查找；
3. 目标值 < 当前节点值：目标值只可能在左子树，跳转到左孩子继续查找；
4. 目标值 = 当前节点值：查找成功，返回对应结果；
5. 最多查找树的高度次，遍历到空节点仍未匹配：查找失败，返回对应结果。

特殊规则补充：如果BST支持插入相等的值，意味着树中可能存在多个相同key，一般要求查找时返回中序遍历的第一个匹配key。

示例：在根节点为8的BST中查找7

• 7 < 8 → 跳转到左孩子3；
• 7 > 3 → 跳转到右孩子6；
• 7 > 6 → 跳转到右孩子7；
• 匹配成功，查找结束，全程仅4次比对。

3.3 查找操作的代码实现（key模型）

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
        {
            // 找到目标key，查找成功
            return true;
        }
    }
    // 遍历至空仍未找到，查找失败
    return false;
}

3.4 补充知识：while(cin >> x)的底层原理

老师在查找测试环节补充：while(cin >> x)能持续接收输入，核心是C++的istream类重载了operator bool：

1. 当输入正常、流状态无错误时，转换后的布尔值为true，循环继续；
2. 当输入类型不匹配、或输入EOF（Windows下为Ctrl+Z+换行）时，转换后的布尔值为false，循环终止。

四、二叉搜索树的时间复杂度分析与核心缺陷

4.1 时间复杂度的决定因素

BST的查找、插入、删除操作，都只需要遍历树的一条路径，时间复杂度完全由树的高度决定，而非节点总数n。

4.2 理想情况：O(log₂N)

当树的左右子树分布均匀，接近满二叉树/完全二叉树时，树的高度为log₂N，此时所有操作的时间复杂度均为O(log₂N)，效率极高。

老师用直观数据展示了O(log₂N)的优势：

数据量n	log₂n（最多查找次数）	暴力查找最多次数
1000	10次	1000次
100万	20次	100万次
10亿	30次	10亿次

4.3 最坏情况：O(N)

当插入的数据是有序/接近有序时，BST会退化成单支树（结构等同于链表），此时树的高度等于节点总数N，所有操作的时间复杂度退化到O(N)，和暴力查找无任何区别。

4.4 综合时间复杂度与核心缺陷

综合最优与最坏情况，二叉搜索树增删查改的整体时间复杂度为O(N)，这样的效率无法满足工业级开发的需求。

【核心结论】原生二叉搜索树直接使用可靠性不足，极端场景下效率会急剧退化，因此需要引入平衡二叉搜索树，通过控制树的平衡，将高度稳定在log₂N级别，才能真正适用于内存中数据的存储与搜索。

4.5 平衡二叉搜索树的引入

平衡二叉搜索树的核心目标：让树的左右子树分布更均匀，避免退化成单支树，将时间复杂度稳定在O(log₂N)。
工业界主流的两种实现：

1. AVL树：严格平衡，通过旋转操作控制左右子树的高度差不超过1；
2. 红黑树：通过节点颜色标记实现相对平衡，性能更优，是C++ STL容器的底层实现。

五、二叉搜索树 vs 二分查找

二分查找也能实现O(log₂N)级别的查找效率，但存在两大致命缺陷，这也是平衡二叉搜索树的核心价值所在：

特性	二叉搜索树	二分查找
存储要求	无特殊要求，链式存储	必须有序，且支持随机访问（仅数组、deque）
插入/删除效率	无需挪动数据，效率高	中间插入/删除需挪动大量数据，O(n)效率极低
适配场景	动态数据（高频增删查）	静态数据（极少增删、高频查询）

【老师补充】排序的代价并非二分查找的最大问题，因为排序一次可支持多次查找；真正的致命缺陷是无法适配高频增删的动态数据场景，而这正是业务开发中的主流场景。

六、二叉搜索树的完整实现（key模型）

key模型：节点仅存储关键字key，核心用途是判断“值是否存在”，对应C++ STL中的set容器。

【核心限制】key模型的二叉搜索树仅支持增删查，不支持修改key，修改key会直接破坏二叉搜索树的结构规则。

6.1 节点结构定义

template<class K>
struct BSTreeNode
{
    BSTreeNode<K>* _left;  // 左孩子指针
    BSTreeNode<K>* _right; // 右孩子指针
    K _key;                 // 关键字，用于比较排序

    // 节点构造函数
    BSTreeNode(const K& key)
        :_left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}
};

【补充说明】

• 模板参数K要求必须支持<、>、==比较运算符；
• 使用struct而非class：让成员默认公有，方便树的内部操作，避免友元声明的冗余；最终节点会封装在树类的私有区域，外层无法访问，无安全性问题。

6.2 树类的基础框架

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node; // 简化节点类型名
private:
    Node* _root = nullptr; // 根节点，默认初始化为空

    // 私有递归函数，外部无法直接调用
    void _InOrder(Node* root);
    void Destory(Node* root);
    Node* Copy(Node* root);

public:
    // 强制生成默认构造函数（C++11）
    BSTree() = default;
    // 拷贝构造函数（深拷贝）
    BSTree(const BSTree<K>& t);
    // 赋值运算符重载
    BSTree<K>& operator=(BSTree<K> t);
    // 析构函数
    ~BSTree();

    // 核心操作成员函数
    bool Insert(const K& key);
    bool Find(const K& key);
    bool Erase(const K& key);
    void InOrder();//中序遍历
};

6.3 插入操作（Insert）

插入核心规则

1. 树为空，则直接新增结点，赋值给root指针；
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点；
3. 本次实现默认不支持冗余key，key已存在时插入失败，返回false；
4. 新插入的节点最终一定位于叶子节点（空指针位置）；
5. 若支持插入相等的值，需保持逻辑一致性，统一往左或往右走找到空位置插入。

新手必踩坑

不能直接把新节点赋值给遍历指针cur：cur是循环内的局部变量，仅修改cur的值不会改变树的结构，必须通过父节点parent的_left/_right指针赋值，才能真正把节点插入到树中，建立正确的链接关系。

完整代码实现

bool Insert(const K& key)
{
    // 情况1：树为空，直接创建根节点
    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
        {
            // 情况2：key已存在，不支持冗余，插入失败
            return false;
        }
    }

    // 找到空位置，创建新节点
    cur = new Node(key);
    // 将新节点链接到父节点的对应位置
    if (parent->_key < key)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

    return true;
}

6.4 中序遍历（InOrder）

通过套一层函数的方式解决私有根节点的访问问题：外部调用无参的InOrder，内部调用私有的递归函数_InOrder并传入根节点，这是C++类中实现二叉树递归的惯用写法。

// 外部调用的无参遍历函数
void InOrder()
{
    _InOrder(_root);
    cout << endl;
}

// 内部递归的中序遍历函数
private:
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    // 中序遍历规则：左子树 → 根节点 → 右子树
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

6.5 删除操作（Erase）【核心难点，分步推演】

删除是BST最复杂的操作，极易出现空指针崩溃、树结构破坏等问题，老师将其分为4种场景处理，其中前3种可合并，第4种为核心难点。

前置步骤

先通过遍历找到要删除的节点cur，同时记录其父节点parent；若遍历到空仍未找到目标key，删除失败，返回false。

场景分类与处理逻辑

场景编号	节点情况	核心处理逻辑（老师形象比喻：托孤）
1	左右孩子均为空（叶子节点）	无孩子需要托付，直接删除节点，父节点对应指针置空（可当成场景2/3处理，效果一致）
2	左孩子为空，右孩子不为空	把右孩子托付给父节点，父节点对应指针指向右孩子，再删除当前节点
3	右孩子为空，左孩子不为空	把左孩子托付给父节点，父节点对应指针指向左孩子，再删除当前节点
4	左右孩子均不为空	无法直接托孤，找替代节点替换当前节点的值，再删除替换后的叶子节点

【核心优化】场景1可合并到场景2或场景3中，无需单独写逻辑：叶子节点左右都为空，左为空可按场景2处理，右为空可按场景3处理。

致命坑点1：删除根节点的特殊处理

当要删除的节点是根节点时，parent为nullptr，若直接访问parent->_left/parent->_right会触发空指针解引用，导致程序崩溃。必须单独处理：直接修改根节点_root，让其指向托付的孩子节点，可通过parent == nullptr或cur == _root两种方式判断根节点。

场景1-3的代码实现

// 找到目标节点，分情况删除
if (cur->_left == nullptr)
{
    // 场景1：左右都空；场景2：左空右非空
    if (parent == nullptr) //特殊处理根节点： 等价于 cur == _root，判断是否为根节点
    {
        // 特殊处理：删除的是根节点，无父节点
        _root = cur->_right;
    }
    else
    {
        // 判断cur是父节点的左还是右孩子，对应修改父节点指针
        if (cur == parent->_left)
        {
            parent->_left = cur->_right;
        }
        else
        {
            parent->_right = cur->_right;
        }
    }
    delete cur;
}
else if (cur->_right == nullptr)
{
    // 场景3：右空左非空
    if (parent == nullptr) // 等价于 cur == _root，判断是否为根节点
    {
        // 特殊处理：删除的是根节点
        _root = cur->_left;
    }
    else
    {
        if (cur == parent->_left)
        {
            parent->_left = cur->_left;
        }
        else
        {
            parent->_right = cur->_left;
        }
    }
    delete cur;
}

场景4：左右孩子均不为空的替换法处理

核心原理：必须找一个能完美替代当前节点的节点，要求其值比左子树所有值大，比右子树所有值小，符合条件的节点只有两个，任选其一即可：

1. 当前节点右子树的最小节点（最左节点）：右子树中最小的值，天然满足比左子树全大、比右子树其他值全小；
2. 当前节点左子树的最大节点（最右节点）：左子树中最大的值，同样满足替换条件。

老师统一使用右子树的最小节点实现，步骤如下：

1. 找到当前节点右子树的最小节点minRight，同时记录其父节点pMinRight；
2. 交换当前节点和minRight的key值，把要删除的key换到叶子节点位置；
3. minRight是最左节点，左孩子一定为空，可直接用场景2的逻辑删除。

致命坑点2：minRight是当前节点的直接右孩子
当当前节点的右孩子本身就是最左节点（右孩子的左为空），循环不会执行，minRight是pMinRight的右孩子，而非左孩子。若默认按左孩子处理，会导致指针赋值错误，程序崩溃。

修复方案：删除前判断minRight是父节点的左还是右孩子，对应修改父节点的指针。

场景4的代码实现（从有坑到修复）

【初始有坑版本】

else // 两个孩子都不为空
{
    Node* pMinRight = cur;
    Node* minRight = cur->_right;
    // 找右子树的最左节点（最小值）
    while (minRight->_left)
    {
        pMinRight = minRight;
        minRight = minRight->_left;
    }
    // 交换key值
    swap(cur->_key, minRight->_key);
    // 有坑：默认minRight是pMinRight的左孩子，循环未执行时会出错
    pMinRight->_left = minRight->_right;
    delete minRight;
}

【修复后的正确版本】

else // 两个孩子都不为空
{
    Node* pMinRight = cur;
    Node* minRight = cur->_right;
    // 找右子树的最左节点（最小值）
    while (minRight->_left)
    {
        pMinRight = minRight;
        minRight = minRight->_left;
    }
    // 交换key值，把要删除的key换到叶子节点
    cur->_key = minRight->_key; // 等价于swap(cur->_key, minRight->_key)

    // 修复坑点：判断minRight是父节点的左还是右孩子
    if (pMinRight->_left == minRight)
    {
        pMinRight->_left = minRight->_right;
    }
    else
    {
        pMinRight->_right = minRight->_right;
    }
    // 删除替换后的节点
    delete minRight;
}

删除操作的完整最终代码

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
        {
            // 第二步：找到节点，分情况删除
            if (cur->_left == nullptr)
            {
                // 左为空，用右孩子托孤
                if (parent == nullptr)
                {
                    _root = cur->_right;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        parent->_left = cur->_right;
                    }
                    else
                    {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
            }
            else if (cur->_right == nullptr)
            {
                // 右为空，用左孩子托孤
                if (parent == nullptr)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        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;
                }
                // 交换key值
                cur->_key = minRight->_key;
                // 删除替换后的节点
                if (pMinRight->_left == minRight)
                {
                    pMinRight->_left = minRight->_right;
                }
                else
                {
                    pMinRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    // 未找到目标节点，删除失败
    return false;
}

七、BST的深拷贝：拷贝构造、析构与赋值重载

编译器默认生成的拷贝构造是浅拷贝，会导致两个树的根节点指向同一块内存，出现两个问题：

1. 一个树修改节点，另一个树会被同步影响；
2. 析构时同一块内存会被释放两次，导致程序崩溃。
   因此必须实现深拷贝，为新树创建独立的节点和内存空间。

7.1 析构函数

析构需要释放树中所有节点，必须使用后序遍历：先释放左子树，再释放右子树，最后释放当前节点。若先释放当前节点，会丢失左右孩子的地址，导致内存泄漏。

// 析构函数
~BSTree()
{
    Destroy(_root);
    _root = nullptr;
}

private:
// 递归释放节点，后序遍历实现
void Destroy(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    // 后序规则：左子树 → 右子树 → 根节点
    Destroy(root->_left);
    Destroy(root->_right);
    // 最后释放当前节点
    delete root;
}

7.2 拷贝构造函数

深拷贝需要创建一棵和原树结构、数值完全一致的新树，使用前序遍历实现：先拷贝当前根节点，再递归拷贝左子树，最后递归拷贝右子树。

【易错警告】不能通过遍历原树的中序结果再逐个Insert实现拷贝！插入顺序不同会导致树的形状和原树完全不同，即使中序结果一致，也失去了拷贝的意义。必须通过前序递归保证树的结构完全一致。

// 拷贝构造函数
BSTree(const BSTree<K>& t)
{
    _root = Copy(t._root);
}

private:
// 递归拷贝节点，前序遍历实现
Node* Copy(Node* root)
{
    if (root == nullptr)
    {
        return nullptr;
    }
    // 前序规则：先拷贝当前根节点
    Node* copyNode = new Node(root->_key);
    // 再递归拷贝左、右子树
    copyNode->_left = Copy(root->_left);
    copyNode->_right = Copy(root->_right);
    // 返回拷贝好的节点，建立链接关系
    return copyNode;
}

7.3 赋值运算符重载（现代写法）

老师使用C++现代写法，通过传值传参+swap交换实现，代码简洁且异常安全：

1. 传值传参时，编译器自动调用拷贝构造函数，创建临时对象t；
2. 交换当前对象和临时对象的根节点，当前对象拿到拷贝好的新树；
3. 函数结束后，临时对象自动析构，释放原来的旧内存。

// 赋值运算符重载
BSTree<K>& operator=(BSTree<K> t)
{
    // 交换当前对象和临时对象的根节点
    swap(_root, t._root);
    // 返回当前对象，支持连续赋值
    return *this;
}

【语法补充】写了拷贝构造函数后，编译器不会再生成默认的无参构造函数，因此需要用BSTree() = default;强制生成默认构造函数（C++11语法）。

八、BST的KV模型（key-value模型）

KV模型是工业界更常用的形态，也是C++ STL中map容器的底层原理，核心是通过key快速查找并获取关联的value。

8.1 KV模型的核心定义

• 每个节点不仅存储用于比较的关键字key，还存储一个和key关联的值value；
• 所有插入、查找、删除操作仅通过key进行，value不参与任何比较，仅用于存储关联数据；
• key不允许修改（会破坏BST结构），但value可以任意修改，不影响树的排序规则。

8.2 KV模型的节点结构定义

template<class K, class V>
struct BSTreeNode
{
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;   // 关键字，用于比较，唯一标识
    V _value; // 关联的值，不参与比较

    // 节点构造函数
    BSTreeNode(const K& key, const V& value)
        :_left(nullptr)
        , _right(nullptr)
        , _key(key)
        , _value(value)
    {}
};

8.3 KV模型的核心操作差异

1. 插入函数：需要同时传入key和value，比较逻辑仅看key，和key模型完全一致。

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
        {
            // key已存在，插入失败
            return false;
        }
    }

    cur = new Node(key, value);
    if (parent->_key < key)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    return true;
}

2. 查找函数：不再返回bool，而是返回节点指针Node*。找到key返回对应节点指针，可通过指针获取/修改value；未找到返回nullptr。

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;
}

3. 删除函数：逻辑和key模型完全一致，仅通过key查找和删除，value不参与任何逻辑。
4. 中序遍历：同时输出key和对应的value，验证树的结构正确性。

private:
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    _InOrder(root->_left);
    // 同时输出key和关联的value
    cout << root->_key << ":" << root->_value << endl;
    _InOrder(root->_right);
}

5. 深拷贝相关函数：逻辑与key模型完全一致，仅节点构造时需要同时传入key和value。

private:
// 递归拷贝节点，前序遍历实现
Node* Copy(Node* root)
{
    if (root == nullptr)
        return nullptr;
    Node* newRoot = new Node(root->_key, root->_value);
    newRoot->_left = Copy(root->_left);
    newRoot->_right = Copy(root->_right);
    return newRoot;
}

// 递归释放节点，后序遍历实现
void Destroy(Node* root)
{
    if (root == nullptr)
        return;
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
}

九、BST的实际应用场景

9.1 key模型的应用场景

核心需求：单纯判断一个值“在不在”，无需存储额外关联数据。

1. 小区无人值守车库门禁系统：将小区买了车位的业主车牌号录入BST，车辆进入时扫描车牌，通过Find判断是否在系统中，在则抬杆放行，不在则提示非本小区车辆，无法进入。
2. 英文单词拼写检查：将词库中所有正确的英文单词放入BST，读取文章中的每个单词，查找是否在二叉搜索树中，不在则波浪线标红提示拼写错误。
3. 安防人脸识别系统：将目标人脸的特征值录入BST，摄像头抓取人脸后，提取特征值快速匹配，判断是否为目标人员。

9.2 KV模型的应用场景

核心需求：通过key快速查找并获取对应的关联value，是业务开发中的主流场景。

1. 简单中英互译字典：树的节点中存储key（英文单词）和value（对应的中文释义）。输入英文单词，通过Find找到节点，返回对应的中文翻译。
2. 商场无人值守车库计费系统：key为车牌号，value为车辆入场时间。车辆入场时Insert车牌号和当前系统时间；车辆出场时Find车牌号，获取入场时间，用当前时间减去入场时间计算出停车时长，最终核算停车费用，缴费后抬杆放行。
3. 文章单词词频统计：key为单词，value为单词出现的次数。遍历文章中的单词，先Find单词：
   • 未找到：说明单词第一次出现，Insert(单词, 1)；
   • 已找到：将对应节点的value（出现次数）自增。
     遍历完成后，中序遍历即可得到按单词升序排列的词频统计结果。

【老师补充说明】
上述场景在实际工业界中，不会直接用内存中的原生BST实现：内存中的数据会在程序崩溃、断电时丢失，长期存储的数据会使用数据库实现，而数据库索引的底层是B树/B+树（BST的进阶版本）；内存中的高频查找场景，会使用平衡二叉搜索树（红黑树）实现，也就是C++ STL中的set和map容器。