🎯 本节目标

1. 内容安排说明 📋
2. 二叉搜索树实现 🌳
3. 二叉树搜索树应用分析 🔍
4. 二叉树进阶面试题 💡

---

1. 内容安排说明 📋

二叉树在C语言数据结构阶段已经讲过，本节取名“二叉树进阶”主要有以下几个原因：

1. 为map和set铺垫：map和set的特性需要先理解二叉搜索树，而二叉搜索树本身就是一种树形结构。
2. 深入理解特性：了解二叉搜索树的特性，有助于更好地理解map和set的底层实现原理。
3. 面试题难度提升：二叉树部分有些面试题难度稍大，前期讲解不易接受，且时间久了容易遗忘。
4. C++实现优势：有些OJ题用C语言实现比较麻烦（比如需要返回动态开辟的二维数组），而C++实现更加简洁高效。

因此，本节将借助二叉搜索树，对二叉树知识进行收尾总结，并引入一些高阶面试题。

---

2. 二叉搜索树 🌳

2.1 二叉搜索树概念

二叉搜索树（Binary Search Tree，BST），又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

• 左子树性质：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
• 右子树性质：若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
• 递归性质：它的左右子树也分别为二叉搜索树。

简单来说：对于BST中的任意节点，其左子树的所有节点值都小于它，右子树的所有节点值都大于它。

2.2 二叉搜索树操作

🔍 查找操作

1. 从根节点开始比较。
2. 若查找值比当前节点值大，则向右子树查找。
3. 若查找值比当前节点值小，则向左子树查找。
4. 最多查找树的高度次，若走到空节点还未找到，则该值不存在。

➕ 插入操作

1. 树为空：直接创建新节点作为根节点。
2. 树不空：按照二叉搜索树的性质找到插入位置（找到某个叶子节点的空孩子位置），插入新节点。
   

❌ 删除操作（重点！）

首先查找要删除的节点是否存在，若不存在则直接返回。要删除的节点可能有以下四种情况：

情况	描述	处理方式
a	要删除的节点是叶子节点（无孩子）	直接删除，将其父节点对应指针置空
b	要删除的节点只有左孩子	用左孩子替代该节点（父节点指向左孩子）
c	要删除的节点只有右孩子	用右孩子替代该节点（父节点指向右孩子）
d	要删除的节点有左右孩子	替换法删除（最复杂）

情况d（替换法删除）的详细步骤：

1. 找到待删除节点右子树中的最小节点（即右子树中最左边的节点），或者左子树中的最大节点（即左子树中最右边的节点）。这里以找右子树最小节点为例。
2. 用这个“最小节点”的值覆盖待删除节点的值。
3. 此时问题转化为删除这个“最小节点”，而这个最小节点必定满足情况a或情况c（因为它是最左边的节点，最多只有一个右孩子），按对应情况删除即可。

示例数组：int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

2.3 二叉搜索树的实现（C++）

下面是一个完整的二叉搜索树实现，包含节点结构、查找、插入、删除和中序遍历。

#include <iostream>
using namespace std;

// 二叉搜索树节点模板类
template<class T>
struct BSTNode {
    BSTNode(const T& data = T())
        : _left(nullptr), _right(nullptr), _data(data) {}
    
    BSTNode<T>* _left;  // 左孩子指针
    BSTNode<T>* _right; // 右孩子指针
    T _data;            // 节点值
};

// 二叉搜索树模板类
template<class T>
class BSTree {
    typedef BSTNode<T> Node;
public:
    BSTree() : _root(nullptr) {}
    
    // 析构函数：释放所有节点内存
    ~BSTree() {
        _Destroy(_root);
    }
    
    // 查找值为data的节点
    Node* Find(const T& data) {
        Node* cur = _root;
        while (cur) {
            if (data < cur->_data) {
                cur = cur->_left;
            } else if (data > cur->_data) {
                cur = cur->_right;
            } else {
                return cur; // 找到
            }
        }
        return nullptr; // 未找到
    }
    
    // 插入值为data的节点
    bool Insert(const T& data) {
        // 1. 树为空，直接插入为根节点
        if (_root == nullptr) {
            _root = new Node(data);
            return true;
        }
        
        // 2. 查找插入位置
        Node* cur = _root;
        Node* parent = nullptr; // 记录cur的父节点
        while (cur) {
            parent = cur;
            if (data < cur->_data) {
                cur = cur->_left;
            } else if (data > cur->_data) {
                cur = cur->_right;
            } else {
                // 值已存在，插入失败
                return false;
            }
        }
        
        // 3. 插入新节点
        cur = new Node(data);
        if (data < parent->_data) {
            parent->_left = cur;
        } else {
            parent->_right = cur;
        }
        return true;
    }
    
    // 删除值为data的节点
    bool Erase(const T& data) {
        // 树为空，删除失败
        if (_root == nullptr) return false;
        
        Node* cur = _root;
        Node* parent = nullptr;
        
        // 1. 查找待删除节点
        while (cur) {
            if (data == cur->_data) {
                break; // 找到
            } else if (data < cur->_data) {
                parent = cur;
                cur = cur->_left;
            } else {
                parent = cur;
                cur = cur->_right;
            }
        }
        
        // 未找到待删除节点
        if (cur == nullptr) return false;
        
        // 2. 分情况删除
        // 情况b & c：待删除节点最多只有一个孩子
        if (cur->_left == nullptr) {
            // 只有右孩子或无孩子
            if (cur == _root) {
                _root = cur->_right;
            } else {
                if (parent->_left == cur) {
                    parent->_left = cur->_right;
                } else {
                    parent->_right = cur->_right;
                }
            }
            delete cur;
        } else if (cur->_right == nullptr) {
            // 只有左孩子
            if (cur == _root) {
                _root = cur->_left;
            } else {
                if (parent->_left == cur) {
                    parent->_left = cur->_left;
                } else {
                    parent->_right = cur->_left;
                }
            }
            delete cur;
        } else {
            // 情况d：待删除节点有左右两个孩子（替换法删除）
            // 找右子树的最小节点（最左节点）
            Node* minRight = cur->_right;
            Node* minRightParent = cur;
            while (minRight->_left) {
                minRightParent = minRight;
                minRight = minRight->_left;
            }
            
            // 用minRight的值覆盖cur的值
            cur->_data = minRight->_data;
            
            // 删除minRight节点（minRight最多只有一个右孩子）
            if (minRightParent->_left == minRight) {
                minRightParent->_left = minRight->_right;
            } else {
                minRightParent->_right = minRight->_right;
            }
            delete minRight;
        }
        return true;
    }
    
    // 中序遍历（递归）
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    
private:
    Node* _root;
    
    // 递归销毁子树
    void _Destroy(Node* root) {
        if (root == nullptr) return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
    
    // 递归中序遍历
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_data << " ";
        _InOrder(root->_right);
    }
};

// 测试函数
int main() {
    BSTree<int> tree;
    int arr[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    
    // 插入测试
    for (int num : arr) {
        tree.Insert(num);
    }
    
    cout << "中序遍历结果: ";
    tree.InOrder(); // 输出：1 3 4 6 7 8 10 13 14
    
    // 查找测试
    cout << "查找 6: " << (tree.Find(6) ? "找到" : "未找到") << endl;
    cout << "查找 99: " << (tree.Find(99) ? "找到" : "未找到") << endl;
    
    // 删除测试
    tree.Erase(6);
    cout << "删除6后中序遍历: ";
    tree.InOrder(); // 输出：1 3 4 7 8 10 13 14
    
    tree.Erase(8); // 删除根节点
    cout << "删除8后中序遍历: ";
    tree.InOrder(); // 输出：1 3 4 7 10 13 14
    
    return 0;
}

2.4 二叉搜索树的应用 🔍

二叉搜索树主要有两种模型：

1. K模型（Key模型）

• 特点：只有key作为关键码，结构中只需要存储key。
• 应用场景：判断某个值是否存在。
• 示例：单词拼写检查
  • 以词库中所有单词作为key，构建一棵二叉搜索树。
  • 查询时，在树中检索该单词是否存在。

2. KV模型（Key-Value模型）

• 特点：每个关键码key都对应一个值value，即<key, value>键值对。
• 应用场景：需要通过key查找或统计对应value。
• 示例1：英汉词典
  • key：英文单词，value：中文翻译。
• 示例2：统计单词出现次数
  • key：单词，value：出现次数。

KV模型二叉搜索树改造示例：

// KV模型的节点
template<class K, class V>
struct BSTreeNode {
    BSTreeNode(const K& key = K(), const V& value = V())
        : _left(nullptr), _right(nullptr), _key(key), _value(value) {}
    
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;
};

// KV模型的二叉搜索树（简略版，插入查找逻辑与K模型类似）
template<class K, class V>
class BSTree {
    typedef BSTreeNode<K, V> Node;
public:
    BSTree() : _root(nullptr) {}
    
    // 查找：根据key找节点
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (key < cur->_key) cur = cur->_left;
            else if (key > cur->_key) cur = cur->_right;
            else return cur;
        }
        return nullptr;
    }
    
    // 插入key-value对
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }
        
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur) {
            parent = cur;
            if (key < cur->_key) cur = cur->_left;
            else if (key > cur->_key) cur = cur->_right;
            else return false; // key已存在
        }
        
        cur = new Node(key, value);
        if (key < parent->_key) parent->_left = cur;
        else parent->_right = cur;
        return true;
    }
    
    // 中序遍历打印（用于测试）
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    
private:
    Node* _root;
    
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << ":" << root->_value << " ";
        _InOrder(root->_right);
    }
};

// 测试：统计水果出现次数
void TestBSTree4() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    BSTree<string, int> countTree;
    
    for (const auto& str : arr) {
        auto ret = countTree.Find(str);
        if (ret == nullptr) {
            // 第一次出现
            countTree.Insert(str, 1);
        } else {
            // 已存在，次数+1
            ret->_value++;
        }
    }
    
    cout << "水果出现次数统计: ";
    countTree.InOrder(); // 输出：苹果:6 西瓜:3 香蕉:2
}

2.5 二叉搜索树的性能分析 ⚡

插入和删除操作都必须先查找，因此查找效率代表了二叉搜索树各个操作的性能。

对于有n个节点的二叉搜索树，若每个元素查找概率相等，则平均查找长度（ASL）是节点在树中深度的函数——节点越深，比较次数越多。

性能对比：

情况	树的结构	平均查找次数（时间复杂度）	示例（插入顺序不同）
最优	完全二叉树（或接近）	$O(lo{g}_{2}N)$	按{4, 2, 6, 1, 3, 5, 7}插入
最差	退化成单支树（链表）	$O(N)$	按{1, 2, 3, 4, 5, 6, 7}插入

问题：如果插入顺序导致树退化成单支树，二叉搜索树的性能优势就丧失了。能否改进，使得无论按什么次序插入，二叉搜索树的性能都能接近最优？

答案是肯定的！这就需要我们后续学习AVL树和红黑树，它们通过旋转等操作保持树的平衡，从而将时间复杂度稳定在$O(logN)$。

---

3. 二叉树进阶面试题 💡

以下题目更适合用C++完成，难度也更大一些，是面试中的高频考点。每个题目都附上了力扣（LeetCode）链接，方便大家练习。

1. 二叉树创建字符串 - 将二叉树按照特定格式转换成字符串。
2. 二叉树的层序遍历 I - 经典的层序遍历，返回二维数组。
3. 二叉树的层序遍历 II - 自底向上的层序遍历。
4. 二叉树的最近公共祖先 - 找到树中两个节点的最近公共祖先（LCA）。
5. 二叉搜索树与双向链表 - 将二叉搜索树转换成排序的循环双向链表。
6. 从前序与中序遍历序列构造二叉树 - 经典的重建二叉树问题。
7. 从中序与后序遍历序列构造二叉树 - 另一种重建方式。
8. 二叉树的前序遍历（非递归） - 使用栈模拟递归。
9. 二叉树的中序遍历（非递归） - 非递归中序遍历。
10. 二叉树的后序遍历（非递归） - 非递归后序遍历，难度稍大。

---

📌 总结与复习建议

1. 掌握核心：理解二叉搜索树的定义、性质和增删查改操作，特别是删除操作的三种情况。
2. 区分模型：明确K模型（纯查找）和KV模型（键值对）的应用场景。
3. 分析性能：理解二叉搜索树性能不稳定的原因，知道AVL树和红黑树是如何解决这个问题的。
4. 刷题巩固：动手实现一遍完整的BST代码，并尝试解决上面列出的进阶面试题。

二叉搜索树是更高级数据结构（如map、set）的基础，也是面试中的常客。理解透彻后，学习后续的平衡二叉树