Hello 算法：二叉树（Binary Tree）核心概念与实操指南-二趣网

Hello 算法：二叉树（Binary Tree）核心概念与实操指南

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇技术指南以《Hello 算法》仓库中俄语版二叉树章节（ru/docs/chapter_tree/binary_tree.md）为骨架，系统讲解二叉树的定义、节点结构、核心术语、增删操作、四种常见形态与退化问题，并对照仓库内 C 语言、C++、Python 等源码逐一印证实现细节。读完本文，你将掌握二叉树的完整概念体系，并能直接运行仓库代码验证"初始化—插入—删除"全过程，为后续学习二叉搜索树、AVL 树与树的遍历打下基础。

二叉树是什么

二叉树（binary tree）是一种非线性数据结构，表达"祖先"与"后代"之间的关系，体现"分而治之"的逻辑。与链表相似，二叉树的基本组成单位也是节点（node），但每个节点最多包含一个值、一个左子节点引用和一个右子节点引用。

以 Python 为例，节点的典型定义如下（仓库完整实现见 codes/python/modules/tree_node.py）：

class TreeNode: """二叉树节点类""" def __init__(self, val: int): self.val: int = val # 节点值 self.left: TreeNode | None = None # 左子节点引用 self.right: TreeNode | None = None # 右子节点引用

在 C 语言中，节点被实现为结构体，并且额外维护了一个height字段（用于后续 AVL 树的平衡计算），见 codes/c/utils/tree_node.h：

/* 二叉树节点结构体 */ typedef struct TreeNode { int val; // 节点值 int height; // 节点高度 struct TreeNode *left; // 左子节点指针 struct TreeNode *right; // 右子节点指针 } TreeNode; /* 构造函数 */ TreeNode *newTreeNode(int val) { TreeNode *node; node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = val; node->height = 0; node->left = NULL; node->right = NULL; return node; }

Rust 由于所有权机制，采用Rc<RefCell<TreeNode>>包装节点实现共享引用；Go、Java、C#、Swift、JS/TS、Dart、Kotlin、Ruby 等语言的节点定义均可在对应章节目录（如 codes/java/chapter_tree、codes/go/chapter_tree）中找到。

每个节点持有两条引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。给定某个节点，由其左子节点及下方所有节点构成的树称为该节点的左子树（left subtree），同理可定义右子树（right subtree）。

没有子节点的节点称为叶子节点（leaf node），其余节点均含有子节点与非空子树。例如上图中以"节点 2"为父节点时，其左、右子节点分别为"节点 4"和"节点 5"，左子树是"节点 4 及其下方"，右子树是"节点 5 及其下方"。

二叉树常见术语

二叉树术语体系是后续所有树类算法（遍历、搜索、平衡）的共同语言，如下图所示：

根节点（root node）：位于二叉树最顶层、没有父节点的节点。
叶子节点（leaf node）：没有子节点的节点，其两条指针都指向None。
边（edge）：连接两个节点的线段，即节点之间的引用（指针）。
层级（level）：从上到下递增，根节点所在层级为 1。
度（degree）：节点的子节点数量，二叉树中度只可能为 0、1、2。
树的高度（height）：从根节点到最远叶子节点所经过的边数。
节点的深度（depth）：从根节点到该节点所经过的边数。
节点的高度（height）：从该节点到其最远叶子节点所经过的边数。

!!! tip 通常"高度"与"深度"指"经过的边数"，但部分教材或题目将其定义为"经过的节点数"，此时高度与深度均需在数值上加 1。阅读题目时务必先确认口径。

二叉树基本操作

初始化二叉树

与链表类似，二叉树的初始化分为两步：先初始化节点，再在节点间建立引用（指针）。以下以仓库 codes/c/chapter_tree/binary_tree.c 中的驱动代码为例：

/* 初始化二叉树 */ // 初始化节点 TreeNode *n1 = newTreeNode(1); TreeNode *n2 = newTreeNode(2); TreeNode *n3 = newTreeNode(3); TreeNode *n4 = newTreeNode(4); TreeNode *n5 = newTreeNode(5); // 构建节点之间的引用（指针） n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5;

这里构建的二叉树形态为：n1为根，n2、n3为其左右子节点，n4、n5为n2的左右子节点。仓库为每种语言都提供了同名驱动文件（如 codes/python/chapter_tree/binary_tree.py、codes/cpp/chapter_tree/binary_tree.cpp），代码逻辑完全一致，可直接对照学习。C 语言版本还支持通过 arrayToTree 用数组快速构建二叉树，序列化规则可参考仓库内数组表示二叉树章节。

插入与删除节点

与链表一样，二叉树的插入与删除通过修改指针即可完成，时间复杂度为 O(1)。以下图为例，演示在n1 -> n2之间插入节点 P，再将其删除：

对应 C 代码（见 codes/c/chapter_tree/binary_tree.c）：

/* 插入与删除节点 */ TreeNode *P = newTreeNode(0); // 在 n1 -> n2 中间插入节点 P n1->left = P; P->left = n2; // 删除节点 P：让 n1 重新指向 n2 n1->left = n2; // 释放内存（C 语言需手动管理） free(P);

不同语言的差异仅体现在内存管理上：C 语言需要显式free(P)（C++ 用delete P），而 Java、Python、Go、JS/TS 等具备 GC 或自动内存管理的语言则无需手动释放。Rust 版本由于所有权模型，需要借助borrow_mut()修改节点内容（见 codes/rust/chapter_tree/binary_tree.rs）。

!!! tip 需要注意：插入节点可能改变二叉树原有的逻辑结构；而删除节点通常意味着连同其整个子树一起删除。因此在二叉树中，插入与删除通常只是某个更大操作序列的组成部分，很少单独出现。

常见二叉树类型

完美二叉树（Perfect Binary Tree）

完美二叉树的所有层级都被完全填满：叶子节点度为 0，其余所有节点度为 2。若树高为h，则节点总数为 $2^{h+1} - 1$，呈标准指数增长，对应自然界常见的细胞分裂现象。

!!! tip 中文社区中常将完美二叉树称为"满二叉树"。

完全二叉树（Complete Binary Tree）

完全二叉树只允许最底层未填满，且底层节点必须从左到右连续填充。完美二叉树本身也是完全二叉树。完全二叉树因可被紧凑地存储在数组中，是堆（heap）实现的基础。

严格二叉树（Full Binary Tree）

严格二叉树要求所有非叶子节点恰好有两个子节点（即不存在度为 1 的节点），但未对层级的填满程度作要求。仓库中术语对照表见 ru/docs/chapter_tree/summary.md。

平衡二叉树（Balanced Binary Tree）

平衡二叉树要求任意节点的左、右子树高度之差的绝对值不超过 1。这一约束正是仓库 codes/c/chapter_tree/avl_tree.c 中 AVL 树实现的核心判据，也是二叉搜索树退化为链表后通过旋转恢复性能的关键。

二叉树的退化：从完美到链表

当每一层都被节点完全填满时，得到"完美二叉树"；当所有节点都偏向一侧时，二叉树退化为"链表"：

完美二叉树对应最好情况，能充分发挥"分而治之"的优势（各类操作复杂度为 $O(\log n)$）。
链表则是最坏情况，所有操作退化为线性，时间复杂度劣化至 $O(n)$。

两种极端结构的关键指标对比如下表：

完美二叉树	链表
第 $i$ 层节点数	$2^{i-1}$	$1$
高度 $h$ 的树的叶子数	$2^h$	$1$
高度 $h$ 的树的总节点数	$2^{h+1} - 1$	$h + 1$
含 $n$ 个节点的树的高度	$\log_2 (n+1) - 1$	$n - 1$

这一对比解释了为什么二叉搜索树、AVL 树等后续章节要刻意维持树形结构：树的形态直接决定操作复杂度，而平衡性是防止退化、保持 $O(\log n)$ 性能的关键。

动手运行：仓库源码验证

仓库为 C 语言版本提供了完整的 CMake 构建配置（见 codes/c/chapter_tree/CMakeLists.txt），其中binary_tree目标对应本文的初始化与增删示例：

add_executable(avl_tree avl_tree.c) add_executable(binary_tree binary_tree.c) add_executable(binary_tree_bfs binary_tree_bfs.c) add_executable(binary_tree_dfs binary_tree_dfs.c) add_executable(binary_search_tree binary_search_tree.c) add_executable(array_binary_tree array_binary_tree.c)

运行后，程序会依次打印"初始化二叉树""插入节点 P 后""删除节点 P 后"三种树形态，直观印证指针修改的效果。此外，codes/c/chapter_tree/binary_tree_bfs.c 展示了借助辅助队列实现的层序遍历（BFS），其中levelOrder函数先让根节点入队，随后循环出队并将左右子节点依次入队，输出逐层访问序列——这正是二叉树在"广度优先遍历"场景下的典型应用，也是后续"树的遍历"章节（ru/docs/chapter_tree/binary_tree_traversal.md）的预习内容。

小结

本文完整覆盖了二叉树的核心知识面：

定义：节点含值、左引用、右引用，体现"祖先—后代"与"分而治之"；
术语：根节点、叶子节点、边、层级、度、深度、高度；
操作：初始化（先建节点再连引用）、插入与删除（O(1) 改指针，注意子树整体删除）；
四种类型：完美（满）、完全、严格、平衡二叉树；
退化分析：完美二叉树与链表的复杂度对比，理解保持平衡的必要性。

掌握了这些基础后，可继续阅读仓库内二叉搜索树、AVL 树与二叉树遍历章节，并对照各语言源码（C/C++/Java/Python/Go/Rust 等）逐一验证。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析