本文是 C++ 面向对象核心（多态、虚函数、绑定机制）与数据结构二叉搜索树（BST）的全程学习复习笔记，完整覆盖核心原理、代码实现、实操踩坑与 bug 修正，所有内容均来自学习过程中的真实疑问与易错点，适合期末复习、面试复盘使用，重点攻克动态绑定底层逻辑、BST 删除操作的核心难点。
第一部分 C++ 多态核心知识点
1.1 多态的核心定义
多态是面向对象三大特性（封装、继承、多态）的核心，本质是同一接口，不同实现：用基类的统一接口，调用不同子类的差异化实现，实现接口复用与逻辑解耦。
多态分为两类：
静态多态（编译期多态）：编译期就确定函数调用地址，由静态绑定实现，比如函数重载、运算符重载
动态多态（运行期多态）：编译期不确定调用地址，运行时才根据真实对象类型确定，由动态绑定实现，也是我们常说的 “多态”
1.2 静态绑定 vs 动态绑定（核心对比）
绑定的本质：确定函数调用的内存地址，二者的核心区别在于绑定时机不同。
表格
特性    静态绑定（早绑定）    动态绑定（晚绑定）
绑定时机    编译期    程序运行时
核心依赖    变量的编译时类型    继承 + virtual 虚函数 + 虚表 vtable
调用方式    直接 call 固定内存地址    取对象 vptr→查虚表→取函数指针→间接调用
触发场景    普通函数 / 成员函数、函数重载、对象直接调用、final 修饰的函数 / 类    1. 存在继承关系 2. 子类重写基类 virtual 虚函数 3. 基类指针 / 引用指向子类对象
性能    极高，编译器可内联优化    略低，有虚表寻址的轻微开销
核心特点    看编译时的指针类型，是什么类型就调谁的函数    看运行时的真实对象类型，指向谁就调谁的函数
必背口诀：静态绑定编译定地址，动态绑定运行查表找实现。
1.3 函数指针的完整获取方式
函数指针是实现动态绑定、虚表的底层基础，不同类型函数的指针获取方式有严格区别：
1.3.1 普通全局 / 自由函数
函数名本身就是函数的入口地址，两种写法等效：
cpp
运行
// 定义函数
void func(int a) { }
// 定义函数指针类型
void (*fp)(int);
// 获取指针
fp = func;      // 简写，函数名隐式转为地址
fp = &func;     // 标准取地址写法，效果完全一致
1.3.2 类普通成员函数（非静态）
成员函数自带隐含this指针，函数指针必须带类作用域，且必须显式取地址：
cpp
运行
class A {
public:
    void fun(int x) { }
};
// 成员函数指针定义
void (A::*fp)(int) = &A::fun;
// 调用方式（必须绑定类对象）
A obj;
(obj.*fp)(10);
1.3.3 类静态成员函数
静态成员函数无隐含this指针，和全局函数用法完全一致：
cpp
运行
class A {
public:
    static void staFun() {}
};
// 获取与调用
void (*fp)() = A::staFun;
fp();
1.3.4 虚函数指针
语法层面：无法直接通过&类名::虚函数获取到运行时的真实函数地址
底层实现：虚函数的指针会在编译期自动存入虚函数表（vtable，本质是函数指针数组），运行时通过对象头部的虚表指针 vptr找到虚表，再按下标取出对应的虚函数指针完成调用
1.4 派生类虚函数表的完整内容
虚表是存储虚函数指针的只读数组，每个有虚函数的类都有自己的虚表，派生类的虚表内容固定包含 4 类，顺序严格遵循规则：
从基类继承、未被子类重写的虚函数：直接沿用基类的函数指针
子类重写（override）的基类虚函数：同下标覆盖为子类自己的函数指针，不新增下标
子类自己新增的虚函数：按声明顺序追加到虚表的末尾
虚析构函数：只要基类声明了虚析构，派生类的析构函数会自动成为虚函数，存入虚表
示例与验证：
cpp
运行
class Base {
public:
    virtual void f1(){}
    virtual void f2(){}
    virtual ~Base(){}
};

class Derive : public Base {
public:
    void f2() override {} // 重写基类f2
    virtual void f3(){}   // 子类新增虚函数
};
Derive 派生类的虚表按顺序为：Base::f1 → Derive::f2 → Derive::~Derive → Derive::f3
核心规则：虚表前半部分顺序和基类完全一致，保证基类指针访问时的兼容性；重写仅覆盖对应下标，不改变顺序；新增虚函数永远追加在末尾。
1.5 多态实现三要素与高频易错点
实现三要素（缺一不可）
基类中声明virtual虚函数
子类 public 继承基类，并重写（override）对应的虚函数
用基类指针 / 引用指向子类对象，调用虚函数触发动态绑定
高频易错点
构造函数不能是虚函数，构造函数中调用虚函数不会触发多态（对象还未构造完成，虚表未初始化）
基类析构函数必须声明为虚函数，否则用基类指针删除子类对象时，只会调用基类析构，造成内存泄漏
子类重写虚函数时，函数签名（返回值、函数名、参数列表、const 属性）必须和基类完全一致，否则是函数重载而非重写
只有虚函数能触发多态，普通成员函数、静态成员函数都无法实现动态绑定
第二部分 二叉搜索树（BST）完整知识点
2.1 BST 核心定义与必背规则
二叉搜索树（Binary Search Tree，BST）也叫二叉排序树，是基于二分思想的树形数据结构，所有操作都必须遵循以下铁律：
节点的左子树所有节点值 ＜ 该节点值
节点的右子树所有节点值 ＞ 该节点值
左、右子树本身也必须是二叉搜索树
默认无重复节点（重复节点可自定义计数处理）
核心性质：对 BST 执行中序遍历（左→根→右），得到的结果是严格升序的有序序列。
2.2 BST 节点结构定义（C++ 模板）
cpp
运行
template<class T>
struct BSTNode {
    T _data;
    BSTNode<T>* _left;
    BSTNode<T>* _right;

    BSTNode(const T& key)
        :_data(key)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
};

template<class T>
class BSTree {
    typedef BSTNode<T> Node;
public:
    // 成员函数：插入、查找、删除
private:
    Node* _root = nullptr;
};
2.3 查找操作：逻辑 + 代码 + 口诀
核心逻辑
从根节点出发，遵循 “左小右大” 规则遍历：
目标值 == 当前节点值 → 查找成功，返回节点
目标值 < 当前节点值 → 进入左子树继续查找
目标值 > 当前节点值 → 进入右子树继续查找
遍历到空节点 → 查找失败，目标值不存在
完整代码
cpp
运行
// 查找：存在返回true，不存在返回false
bool Find(const T& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_data == key) {
            return true;
        } else if (cur->_data > key) {
            cur = cur->_left;
        } else {
            cur = cur->_right;
        }
    }
    return false;
}
必背口诀：小往左，大往右，相等就命中，遇空就没有。
2.4 插入操作：逻辑 + 踩坑分析 + 修正代码
核心逻辑
空树：直接新建节点作为根节点，插入成功
非空树：按查找逻辑遍历，找到合适的空节点位置
新建节点，根据与父节点的大小关系，挂在父节点的左 / 右孩子位置
节点已存在 → 插入失败（BST 默认无重复节点）
核心特点：插入的节点一定是叶子节点，不会改动原有树结构。
踩坑记录（原错误代码）
cpp
运行
bool Insert(const T& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }
    Node* parent=nullptr;
    Node* total=_root;
    while (total) {
        if (total->_data < key) {
            parent = total;
            total = total->_right;
        }
        else if (total->_data > key) {
            parent = total;
            total = total->_left;
        }
        else {
            return false;
        }
    }
    // 错误1：只在if分支新建节点，else分支total仍为nullptr
    if (parent ->_data<key ) {
        total = new Node(key);
    }
    // 错误2：无论key大小，全部挂在父节点左孩子，违背BST规则
    parent->_left = total;
}
错误分析与修正后代码
核心错误：
新建节点逻辑不完整，仅在 key 大于父节点时新建节点
挂载节点错误，未区分左右孩子，全部挂在左孩子，导致树结构错乱
函数部分分支无返回值，存在未定义行为
修正后完整代码
cpp
运行
bool Insert(const T& key) {
    // 空树直接插入根节点
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;

    // 查找插入位置
    while (cur) {
        if (cur->_data < key) {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_data > key) {
            parent = cur;
            cur = cur->_left;
        }
        else {
            return false; // 节点已存在，插入失败
        }
    }

    // 新建节点，按大小挂载到对应位置
    cur = new Node(key);
    if (parent->_data < key) {
        parent->_right = cur; // 比父节点大，挂右孩子
    } else {
        parent->_left = cur;  // 比父节点小，挂左孩子
    }

    return true;
}
必背口诀：按查找往下走，遇空就新建，小挂左、大挂右，挂成叶子不走变。
2.5 删除操作：全场景拆解 + 核心难点 + 踩坑修正
删除是 BST 最复杂的操作，核心原则是：删除后仍需保持 BST 的 “左小右大” 规则，分三种场景处理。
场景 1：待删除节点是叶子节点（无左右孩子）
处理逻辑：直接断开父节点与该节点的连接，释放节点内存即可。
场景 2：待删除节点只有一个孩子（左孩子 或 右孩子）
处理逻辑：让父节点直接指向待删除节点的唯一孩子，用孩子节点顶替待删除节点的位置，再释放节点内存。
特殊处理：若待删除节点是根节点，直接让根节点指向其唯一孩子。
场景 3：待删除节点左右孩子都存在（核心难点）
这是最复杂的场景，不能直接删除节点，否则左右子树无法拼接，会破坏 BST 规则。
核心解决方案：替身替换法
核心思路：不直接删除中间节点，而是找一个 “好删除的替身节点”，交换数值后，删除替身节点即可。
替身节点的选择（二选一）：
待删除节点左子树的最大值（左子树一路向右走到底的节点，也叫前驱节点）
待删除节点右子树的最小值（右子树一路向左走到底的节点，也叫后继节点）
为什么选这两个节点？
左子树最大值：一定小于待删除节点，大于左子树所有其他节点，替换后仍满足 BST 规则
右子树最小值：一定大于待删除节点，小于右子树所有其他节点，替换后仍满足 BST 规则
这两个节点最多只有一个孩子，属于前两种简单场景，删除难度极低
完整处理步骤
找到待删除节点的替身节点（左子树最大值）
交换待删除节点和替身节点的数值
此时待删除的目标转移到了替身节点
按前两种简单场景，删除替身节点即可
踩坑记录（原错误代码核心问题）
cpp
运行
// 错误核心代码
swap(min->_data, total->_data);
// 错误：默认min一定是minparent的右孩子，直接修改右指针
minparent->_right = min->_left;
delete min;
错误深度分析
核心错误：未判断替身节点 min 是父节点的左孩子还是右孩子，直接固定修改父节点的右指针。
触发 bug 的场景：当待删除节点的左子树没有右分支时，while(min->_right)循环一次都不会执行，此时min是minparent的左孩子，直接修改右指针会导致：
父节点左指针仍指向 min，树结构断链、错乱
父节点右指针被错误赋值，破坏 BST 规则
后续查找、遍历全部异常，甚至程序崩溃
修正后完整删除代码
cpp
运行
bool erase(const T& key) {
    Node* parent = nullptr;
    Node* cur = _root;

    // 查找待删除节点
    while (cur) {
        if (cur->_data < key) {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_data > key) {
            parent = cur;
            cur = cur->_left;
        }
        else {
            // 找到待删除节点，分情况处理
            if (cur->_left && cur->_right) {
                // 场景3：左右孩子都存在，找左子树最大值（替身）
                Node* minParent = cur;
                Node* min = cur->_left;

                // 找左子树最右节点（最大值）
                while (min->_right) {
                    minParent = min;
                    min = min->_right;
                }

                // 交换数值，转移删除目标
                swap(cur->_data, min->_data);

                // 关键：判断替身是父节点的左孩子还是右孩子
                if (minParent->_left == min) {
                    minParent->_left = min->_left;
                } else {
                    minParent->_right = min->_left;
                }

                delete min;
            }
            else {
                // 场景1+2：叶子节点 或 只有一个孩子
                Node* child = cur->_left ? cur->_left : cur->_right;

                // 特殊处理：删除根节点
                if (cur == _root) {
                    _root = child;
                } else {
                    // 挂载到父节点对应位置
                    if (cur == parent->_left) {
                        parent->_left = child;
                    } else {
                        parent->_right = child;
                    }
                }

                delete cur;
            }
            return true;
        }
    }

    // 未找到待删除节点
    return false;
}
必背口诀：无子直接删，单子直接替，双子找最值，赋值再删替；替身左右要判断，循环不进是左孩。
2.6 完整可运行的 BST 模板（含中序遍历）
cpp
运行
template<class T>
struct BSTNode {
    T _data;
    BSTNode<T>* _left;
    BSTNode<T>* _right;

    BSTNode(const T& key)
        :_data(key)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
};

template<class T>
class BSTree {
    typedef BSTNode<T> Node;
public:
    // 插入
    bool Insert(const T& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_data < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;
            }
        }

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

    // 查找
    bool Find(const T& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_data == key) return true;
            else if (cur->_data > key) cur = cur->_left;
            else cur = cur->_right;
        }
        return false;
    }

    // 删除
    bool erase(const T& key) {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_data < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                if (cur->_left && cur->_right) {
                    Node* minParent = cur;
                    Node* min = cur->_left;
                    while (min->_right) {
                        minParent = min;
                        min = min->_right;
                    }
                    swap(cur->_data, min->_data);
                    if (minParent->_left == min)
                        minParent->_left = min->_left;
                    else
                        minParent->_right = min->_left;
                    delete min;
                }
                else {
                    Node* child = cur->_left ? cur->_left : cur->_right;
                    if (cur == _root)
                        _root = child;
                    else {
                        if (cur == parent->_left)
                            parent->_left = child;
                        else
                            parent->_right = child;
                    }
                    delete cur;
                }
                return true;
            }
        }
        return false;
    }

    // 中序遍历（升序输出，验证BST正确性）
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

private:
    Node* _root = nullptr;

    void _InOrder(Node* root) {
        if (!root) return;
        _InOrder(root->_left);
        cout << root->_data << " ";
        _InOrder(root->_right);
    }
};
2.7 BST 高频易错点汇总
插入节点时，必须先记录父节点，否则遍历到空节点后无法挂载新节点
删除节点时，必须处理根节点的特殊情况，避免空指针访问
双子节点删除时，必须判断替身节点是父节点的左 / 右孩子，不能固定修改某一个指针
所有操作必须保证不破坏 “左小右大” 的核心规则，否则 BST 会失效
函数所有分支必须有返回值，避免未定义行为
第三部分 终极复习背诵口诀
多态绑定：静态编译定地址，动态运行查表找
虚表规则：继承未改原样留，重写覆盖同下标，新增虚函数往后排
BST 核心：左小右大根中间，中序遍历升序排
BST 插入：小左大右找空位，遇空新建挂叶子
BST 删除：无子删、单子替，双子找最值，左右必判断