2.2节后习题 - 二叉树

一、判断题

1. 二叉树中每个节点的度最大为2，且左右子节点必须严格区分。

正确

错误

2. 完全二叉树的叶子节点只能出现在最后一层。

正确

错误

二、填空题

3. 深度为 h 的满二叉树的节点总数是 ______。

4. 已知二叉树的中序遍历为 DBEAFC，前序遍历为 ABDECF，则后序遍历为 ______。

三、选择题

5. 以下哪种遍历组合可以唯一确定一棵二叉树？

A前序 + 后序

B前序 + 中序

C后序 + 中序

D层序 + 中序

6. 二叉树的第i层最多有多少个节点？

A2^(i-1)

B2^i

Ci^2

D2*i-1

四、应用题

7. 二叉树重构

给定前序遍历 [3,9,20,15,7] 和中序遍历 [9,3,15,20,7]，请画出对应的二叉树。

答案和解析

解析步骤：

前序根为 3，中序划分左子树（9）和右子树（15,20,7）
右子树前序为 20,15,7，中序为 15,20,7，根为 20
继续递归：20 的左子节点为 15，右子节点为 7

构建过程：

根节点：3
左子树：只有节点 9
右子树：根节点 20，左子节点 15，右子节点 7

五、编程题

8. 判断两棵二叉树是否结构相同

实现一个函数，判断两棵二叉树是否结构相同（节点值相同且结构一致）。

参考代码

cpp

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isSameTree(TreeNode* p, TreeNode* q) {
    // 两个节点都为空，相同
    if (p == nullptr && q == nullptr) return true;
    
    // 一个为空一个非空，不同
    if (p == nullptr || q == nullptr) return false;
    
    // 值不同，不同
    if (p->val != q->val) return false;
    
    // 递归比较左右子树
    return isSameTree(p->left, q->left) && 
           isSameTree(p->right, q->right);
}

思路说明：递归比较两棵树的当前节点值及其左右子树。若两节点均为空则相同；若一个空一个非空则不同；若值不同则不同；否则递归比较左右子树。

9. 字典树插入操作

给定一个字典树和一系列单词，编写一个程序来将这些单词插入到字典树中。

参考代码

cpp

#include <string>
using namespace std;

class Trie {
private:
    struct TrieNode {
        bool isEnd;
        TrieNode* children[26]; // 假设字符串仅包含小写字母
        TrieNode() : isEnd(false) {
            for (int i = 0; i < 26; ++i) 
                children[i] = nullptr;
        }
    };
    TrieNode* root;

public:
    Trie() : root(new TrieNode()) {}

    void insert(string s) {
        TrieNode* current = root;
        for (char ch : s) {
            int index = ch - 'a'; // 字符转换为索引（0~25）
            if (!current->children[index]) {
                current->children[index] = new TrieNode(); // 创建新节点
            }
            current = current->children[index]; // 移动到子节点
        }
        current->isEnd = true; // 标记单词结尾
    }
};

实现细节：

节点结构：每个 TrieNode 包含 isEnd 标记和一个大小为26的子节点数组
插入逻辑：
1. 从根节点开始遍历字符串的每个字符
2. 若字符对应的子节点不存在，则新建节点
3. 移动当前指针到子节点，处理下一个字符
4. 字符串遍历完成后，标记 isEnd 为 true

六、分析题

10. 递归与非递归遍历对比

比较递归和非递归实现二叉树前序遍历的优缺点。

答案

递归实现：

优点：代码简洁易懂，逻辑清晰
缺点：存在栈溢出风险（深度过大时），函数调用开销

非递归实现：

优点：显式用栈控制遍历，适合深度大的树，避免系统栈溢出
缺点：代码复杂度更高，需要手动管理栈

选择建议：

对于一般情况，递归实现更直观
对于可能很深的树或性能要求高的场景，考虑非递归实现

知识点总结

二叉树核心概念

定义特征：节点度 ≤ 2，左右子节点严格区分
特殊类型：满二叉树、完全二叉树、平衡二叉树
重要性质：节点数公式、高度关系

遍历与重构

三种遍历：前序、中序、后序
重构规律：前序/后序 + 中序可唯一确定二叉树
应用场景：表达式树、文件系统

编程要点

递归思想：树结构天然适合递归处理
边界条件：空节点的处理至关重要
字典树：前缀匹配的高效数据结构

实际应用

编译器语法分析树
数据库索引结构
文本搜索与前缀匹配

2.2节后习题 - 二叉树 ​

一、判断题 ​

二、填空题 ​

三、选择题 ​

四、应用题 ​

7. 二叉树重构 ​

五、编程题 ​

8. 判断两棵二叉树是否结构相同 ​

9. 字典树插入操作 ​

六、分析题 ​

10. 递归与非递归遍历对比 ​

知识点总结 ​

二叉树核心概念 ​

遍历与重构 ​

编程要点 ​

实际应用 ​