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.pyclass 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 由于所有权机制采用RcRefCellTreeNode包装节点实现共享引用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^{h1} - 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^{h1} - 1$$h 1$含 $n$ 个节点的树的高度$\log_2 (n1) - 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 等逐一验证。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考