GESP六级树知识点考点总结

一、二叉树基础定义与分类

1. 四种核心二叉树定义与区分

2. 完全二叉树层序判断逻辑

第1题代码原型必考

bool check(TreeNode* root) {
    if(!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()){
        TreeNode* cur = q.front();
        q.pop();
        if(!cur){
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

3. 二叉树核心性质

1. 边数性质：n个节点的二叉树，一定有且仅有n-1条边
2. 完全二叉树高度：根节点深度为1时，高度h = ⌊log₂n⌋ + 1
3. 完全二叉树叶子节点数：n个节点的完全二叉树，叶子节点数= ⌈n/2⌉

4. 常考题型与易错点

• 题型：给定代码判断是否为完全二叉树；给定树结构判断类型；完全二叉树高度、叶子节点数计算
• 易错点：混淆完全二叉树和满二叉树；完全二叉树高度计算错误；认为完满二叉树就是满二叉树

二、二叉树的存储

1. 完全二叉树的数组存储

完全二叉树可以用数组连续高效存储，按层序遍历顺序存储节点，空节点用-1表示。

2. 数组表示完全二叉树的判断规则

层序遍历中，一旦出现空节点，后面所有节点必须都是空节点

三、二叉树的遍历

1. 递归遍历

2. 已知两种遍历求第三种遍历

核心方法：

1. 前序遍历第一个节点是根节点；后序遍历最后一个节点是根节点
2. 中序遍历中，根节点左边是左子树，右边是右子树
3. 递归划分左右子树，重复上述步骤

3. 非递归遍历

深度优先遍历

使用栈

void dfs(TreeNode* root) {
    if(!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()){
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
}

广度优先遍历

使用队列

void bfs(TreeNode* root) {
    if(!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()){
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

4. 遍历的复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(h)

四、二叉搜索树

1. 核心定义与性质

• 对于任意节点，其左子树所有节点的值小于该节点的值小于右子树所有节点的值
• 中序遍历二叉搜索树，得到严格递增的有序序列
• 二叉搜索树的最小值是整棵树的最左节点，最大值是整棵树的最右节点

2. 二叉搜索树合法性判断

错误方法：只判断当前节点和左右孩子的关系
正确方法：递归传递上下界

bool isBST(TreeNode* root, long long minVal, long long maxVal) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
}

3. 二叉搜索树基本操作

查找操作

bool find(TreeNode* root, int x) {
    while (root){
        if (root->val == x) return true;
        root = (x < root->val) ? root->left: root->right;
    }
    return false;
}

插入操作

TreeNode* insert(TreeNode* root, int x) {
    if (!root) return new TreeNode(x);
    if (x < root->val) root->left = insert(root->left, x);
    else root->right = insert(root->right, x);
    return root;
}

删除操作

• 叶子节点：直接删除
• 只有一个孩子：用孩子节点替换当前节点
• 有两个孩子：用右子树的最小值或左子树的最大值替换当前节点，再删除该替换节点

4. 二叉搜索树的退化问题

• 连续插入有序数据，二叉搜索树会退化为单链表
• 退化后的时间复杂度：所有操作从O(logn)退化为O(n)
• 解决方法：使用平衡二叉树

5. 常考题型与易错点

• 题型：二叉搜索树操作代码补全；查找路径判断；时间复杂度分析
• 易错点：认为二叉搜索树的查找时间复杂度一定是O(logn)；删除有两个孩子的节点时替换节点选择错误

五、平衡二叉树

1. 核心定义

• 平衡二叉树是一种特殊的二叉搜索树
• 对于任意节点，其左右子树的高度差的绝对值不超过1
• 左右子树也都是平衡二叉树

2. 核心概念

• 平衡因子：节点的左子树高度减去右子树高度
• 平衡二叉树中，所有节点的平衡因子只能是-1、0、1

3. 核心性质

• 保持了二叉搜索树的所有性质
• 解决了二叉搜索树退化的问题，所有操作的时间复杂度始终为O(logn)

4. 常见平衡二叉树类型

• AVL树：严格平衡，旋转操作频繁
• 红黑树：近似平衡，旋转操作少，应用广泛

六、哈夫曼树与哈夫曼编码

1. 哈夫曼树核心概念

• 带权路径长度：所有叶子节点的权值乘以其到根节点的路径长度之和
• 哈夫曼树：带权路径长度最小的二叉树

2. 哈夫曼树构造方法

1. 将所有字符的频率作为叶子节点的权值，构造n棵只有根节点的二叉树
2. 每次选择权值最小的两棵树合并，新节点的权值为两棵树的权值之和
3. 重复步骤2，直到只剩下一棵树
4. n个叶子节点的哈夫曼树，总节点数为2n-1

3. 哈夫曼编码

• 编码规则：左分支为0，右分支为1
• 核心性质：前缀编码，没有任何一个字符的编码是另一个字符编码的前缀
• 特点：频率越高的字符，编码长度越短；可用于数据压缩
• 唯一性：给定字符集和频率，哈夫曼树和编码不唯一

4. 常考题型与易错点

• 题型：哈夫曼编码性质判断；给定字符频率判断可能的编码；哈夫曼树构造代码补全
• 易错点：认为哈夫曼编码是定长编码；认为哈夫曼树和编码是唯一的

七、高频判断题易错点汇总

1. 哈夫曼编码结果唯一 → 错
2. 100个节点的完全二叉树高度为8 → 错
3. 二叉搜索树退化为链表时，时间复杂度为O(nlogn) → 错
4. 数组{1,2,3,4,-1,6,7}表示完全二叉树 → 错
5. 先递归左右子树再判断叶子节点的代码能正确统计叶子数 → 错
6. 对二叉排序树进行中序遍历得到递增序列 → 对
7. 深度优先搜索使用栈，广度优先搜索使用队列 → 对
8. 二叉搜索树的查找时间复杂度为O(h) → 对