YatDS

Appearance

二叉树的概念 ​

二叉树（Binary Tree）是每个节点最多有两个子节点（左孩子和右孩子）的树结构。它是树结构中最基础、最重要的形式，在计算机科学中有着广泛的应用。

二叉树的基本概念 ​

二叉树的定义 ​

二叉树是一种特殊的树结构，具有以下特点：

  • 每个节点最多有两个子节点：分别称为左孩子（Left Child）和右孩子（Right Child）
  • 子节点有序：左子树和右子树是严格区分的，不能互换
  • 递归定义：一棵二叉树由根节点、左子树和右子树组成，左子树和右子树本身也是二叉树

二叉树的基本术语 ​

术语说明
节点（Node）二叉树的基本单位，包含数据和指向子节点的指针
根节点（Root）二叉树的顶端节点，没有父节点
叶节点（Leaf）没有子节点的节点，也称为终端节点
度（Degree）节点的子节点个数，二叉树中节点度数最大为 2
深度（Depth）从根节点到某节点的路径长度
高度（Height）从某节点到其最远叶节点的路径长度
层（Level）根节点在第 1 层，其子节点在第 2 层，以此类推

二叉树的性质 ​

二叉树具有以下重要性质：

  1. 第 i 层最多有 2i−1 个节点（i≥1）
  2. 深度为 k 的二叉树最多有 2k−1 个节点（k≥1）
  3. 对任何非空二叉树，若叶节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1

二叉树的类型 ​

树的类型

满二叉树（Full Binary Tree） ​

满二叉树是指所有节点要么是叶节点（度为 0），要么有两个子节点（度为 2）的二叉树。

特点：

  • 每个内部节点恰好有两个子节点
  • 所有叶节点在同一层
  • 节点总数为 2k−1（k 为树的深度）

完全二叉树（Complete Binary Tree） ​

完全二叉树是指所有节点按照层序从上到下、从左到右依次排列，且最后一层的叶节点从左到右连续出现的二叉树。

特点：

  • 只有最后一层可以不满
  • 最后一层的节点必须从左到右连续
  • 常用于堆的实现

二叉搜索树（Binary Search Tree, BST） ​

二叉搜索树是一种特殊的二叉树，满足以下性质：

  • 左子树所有节点的值 < 根节点的值 < 右子树所有节点的值
  • 左子树和右子树本身也是二叉搜索树

特点：

  • 支持高效的查找、插入、删除操作
  • 中序遍历可以得到有序序列
  • 平均查找时间复杂度 O(log⁡n)

平衡二叉树（Balanced Binary Tree） ​

平衡二叉树是指左右子树的高度差不超过某个常数（通常为 1）的二叉树。

特点：

  • 保证树的高度相对较低
  • 防止操作效率退化
  • 典型实现有 AVL 树、红黑树等

二叉树的存储结构 ​

顺序存储结构 ​

使用数组存储二叉树，适合完全二叉树：

  • 根节点存储在下标 1 处
  • 对于下标为 i 的节点：
    • 左孩子下标：2i
    • 右孩子下标：2i+1
    • 父节点下标：⌊i/2⌋

链式存储结构 ​

使用指针链接节点，是最常用的存储方式：

cpp
template <typename T>
struct BinaryTreeNode {
    T data;
    std::unique_ptr<BinaryTreeNode> left;
    std::unique_ptr<BinaryTreeNode> right;
};

Baseline 任务: 二叉树的基本操作 ​

任务概述 ​

本模块包含以下任务，学生需要按照难度逐步完成：

任务编号任务名称难度必须完成
T1创建二叉树⭐ 基础✓
T2计算树的深度⭐ 基础✓
T3统计节点数量⭐ 基础✓
T4统计叶节点数量⭐ 基础✓
T5判断满二叉树⭐⭐ 进阶✓
T6判断完全二叉树⭐⭐ 进阶✓
T7计算第 k 层节点数⭐⭐ 进阶○
T8翻转二叉树⭐⭐ 进阶○
T9判断二叉搜索树⭐⭐⭐ 挑战○
T10判断平衡二叉树⭐⭐⭐ 挑战○

⭐ 基础任务 ​

T1: 创建二叉树 ​

任务描述：实现从数组创建完全二叉树的函数。

函数签名：

cpp
std::unique_ptr<BinaryTreeNode<int>> create_tree(const std::vector<int> &data);

输入要求：

  • data：包含节点值的数组，按层序排列

输出要求：

  • 返回创建好的二叉树根节点

示例：

cpp
// 输入: {1, 2, 3, 4, 5, 6, 7}
// 输出: 创建如下二叉树
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7

提示：

  • 使用顺序存储的下标关系：对于下标 i，左孩子为 2i+1，右孩子为 2i+2
  • 可以使用递归或迭代方式实现

T2: 计算树的深度 ​

任务描述：计算二叉树的最大深度（高度）。

函数签名：

cpp
int tree_depth(const BinaryTreeNode<int> *root);

输入要求：

  • root：二叉树的根节点指针

输出要求：

  • 返回树的深度（空树返回 0）

示例：

cpp
// 输入: 深度为 3 的二叉树
// 输出: 3

提示：

  • 树的深度 = max(左子树深度, 右子树深度) + 1
  • 使用递归实现较为简洁

T3: 统计节点数量 ​

任务描述：统计二叉树中的节点总数。

函数签名：

cpp
int count_nodes(const BinaryTreeNode<int> *root);

输入要求：

  • root：二叉树的根节点指针

输出要求：

  • 返回节点总数（空树返回 0）

示例：

cpp
// 输入: 有 7 个节点的二叉树
// 输出: 7

提示：

  • 节点总数 = 左子树节点数 + 右子树节点数 + 1

T4: 统计叶节点数量 ​

任务描述：统计二叉树中的叶节点数量。

函数签名：

cpp
int count_leaves(const BinaryTreeNode<int> *root);

输入要求：

  • root：二叉树的根节点指针

输出要求：

  • 返回叶节点数量（空树返回 0）

示例：

cpp
// 输入: 有 4 个叶节点的二叉树
// 输出: 4

提示：

  • 叶节点：左右子节点都为空的节点
  • 递归判断每个节点是否为叶节点

⭐⭐ 进阶任务 ​

T5: 判断满二叉树 ​

任务描述：判断一棵二叉树是否为满二叉树。

函数签名：

cpp
bool is_full_binary_tree(const BinaryTreeNode<int> *root);

定义回顾：满二叉树的每个节点要么是叶节点（度为 0），要么有两个子节点（度为 2）。

示例：

cpp
// 输入: 满二叉树
//       1
//      / \\
//     2   3
//    / \\
//   4   5
// 输出: true

提示：

  • 检查每个节点：度为 0 或度为 2
  • 不能存在度为 1 的节点

T6: 判断完全二叉树 ​

任务描述：判断一棵二叉树是否为完全二叉树。

函数签名：

cpp
bool is_complete_binary_tree(const BinaryTreeNode<int> *root);

定义回顾：完全二叉树按层序从上到下、从左到右排列，最后一层叶节点连续出现。

示例：

cpp
// 输入: 完全二叉树
//       1
//      / \\
//     2   3
//    / \ /
//   4  5 6
// 输出: true

提示：

  • 使用层序遍历
  • 遇到第一个空节点后，后续所有节点都应为空

T7: 计算第 k 层节点数 ​

任务描述：计算二叉树第 k 层的节点数量。

函数签名：

cpp
int count_nodes_at_level(const BinaryTreeNode<int> *root, int k);

输入要求：

  • root：二叉树的根节点指针
  • k：层数（第 1 层为根节点层）

输出要求：

  • 返回第 k 层的节点数量

示例：

cpp
// 输入: k=3
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: 4 (第 3 层有 4 个节点)

T8: 翻转二叉树 ​

任务描述：将二叉树的所有节点的左右子树交换。

函数签名：

cpp
void invert_tree(BinaryTreeNode<int> *root);

示例： 翻转二叉树

cpp
// 输入: 原始二叉树
//       1
//      / \\
//     2   3
//    / \ / \\
//   4  5 6  7
// 输出: 翻转后
//       1
//      / \\
//     3   2
//    / \ / \\
//   7  6 5  4

提示：

  • 递归交换每个节点的左右子节点
  • 可以使用后序遍历的思路

⭐⭐⭐ 挑战任务 ​

T9: 判断二叉搜索树 ​

任务描述：判断一棵二叉树是否为二叉搜索树（BST）。

函数签名：

cpp
bool is_binary_search_tree(const BinaryTreeNode<int> *root);

定义回顾：BST 满足左子树所有值 < 根节点值 < 右子树所有值。

提示：

  • 不能只比较节点与直接子节点
  • 需要传递上下界范围
  • 或使用中序遍历检查是否有序

T10: 判断平衡二叉树 ​

任务描述：判断一棵二叉树是否为平衡二叉树。

函数签名：

cpp
bool is_balanced_binary_tree(const BinaryTreeNode<int> *root);

定义回顾：平衡二叉树的每个节点左右子树高度差不超过 1。

提示：

  • 计算每个节点的左右子树高度差
  • 可以优化为一边计算高度一边判断平衡

基本操作 ​

创建二叉树 ​

根据给定的数据创建一棵二叉树：

cpp
// 从数组创建完全二叉树
std::unique_ptr<BinaryTreeNode<int>> create_tree(const std::vector<int> &data);

计算树的深度 ​

计算二叉树的最大深度（高度）：

cpp
int tree_depth(const BinaryTreeNode<int> *root);

统计节点数量 ​

统计二叉树中的节点总数：

cpp
int count_nodes(const BinaryTreeNode<int> *root);

统计叶节点数量 ​

统计二叉树中的叶节点数量：

cpp
int count_leaves(const BinaryTreeNode<int> *root);

示例代码 ​

cpp
#include "binary_tree.h"

int main() {
    // 创建一棵二叉树
    auto root = BinaryTreeNode<int>::get_new_node(1);
    root->left = BinaryTreeNode<int>::get_new_node(2);
    root->right = BinaryTreeNode<int>::get_new_node(3);
    root->left->left = BinaryTreeNode<int>::get_new_node(4);
    root->left->right = BinaryTreeNode<int>::get_new_node(5);

    // 计算深度
    std::cout << "树的深度: " << tree_depth(root.get()) << std::endl;

    // 统计节点数
    std::cout << "节点总数: " << count_nodes(root.get()) << std::endl;

    // 统计叶节点数
    std::cout << "叶节点数: " << count_leaves(root.get()) << std::endl;

    return 0;
}

数据结构定义 ​

本项目中使用以下数据结构来表示二叉树（定义在 binary_tree.h）：

cpp
template <typename T>
struct BinaryTreeNode {
    T data;
    std::unique_ptr<BinaryTreeNode> left;
    std::unique_ptr<BinaryTreeNode> right;

    BinaryTreeNode(const T &data);
    BinaryTreeNode(T &&data);
    static std::unique_ptr<BinaryTreeNode> get_new_node(const T &data);
    static std::unique_ptr<BinaryTreeNode> get_new_node(T &&data);
};

提交要求 ​

  1. 所有任务代码需放在 Tree/Baseline/binary_tree 目录下
  2. 每个任务需编写对应的测试文件
  3. 基础任务（T1-T4）必须全部完成
  4. 进阶任务（T5-T8）至少完成 2 个
  5. 挑战任务（T9-T10）可选完成

参考资源 ​