二叉树入门精讲从节点结构到退化分析的完整指南Hello 算法【免费下载链接】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 算法》英文版「二叉树Binary Tree」一章原文档系统讲解二叉树的节点定义、父子与子树关系、常用术语、初始化与增删节点的指针操作、完美/完全/满/平衡四类特殊二叉树以及二叉树退化与最优/最坏结构的量化对比。读完本文你将能够用 Python、Java、C、C、Go、Rust 等主流语言独立搭建一棵二叉树并准确理解与运用高度、深度、度、层等核心概念。二叉树的定义祖先与后代的分治骨架与线性数据结构不同二叉树描述的是节点之间的「祖先—后代」层次关系天然体现了一种「一分为二」的分治模式。同链表一样二叉树的基本单元是节点node每个节点包含三部分一个值value存储该节点的数据一个左孩子引用/指针left指向其左子节点一个右孩子引用/指针right指向其右子节点。每个节点拥有两个引用分别指向左孩子节点left-child node与右孩子节点right-child node该节点同时被称为这两个子节点的父节点parent node。给定二叉树中某个节点后由该节点的左孩子及其下方全部节点构成的树称为该节点的左子树left subtree**右子树right subtree**同理。**在二叉树中每个非叶节点都拥有子节点因而也拥有非空子树。**例如下图中若把节点 2视作父节点则它的左、右孩子分别是节点 4和节点 5左子树由节点 4及其下方节点构成右子树由节点 5及其下方节点构成。这种一节点生两枝、两枝再分叉的结构与自然界细胞分裂的规律同构是后续二叉搜索树、AVL 树、堆与各类分治算法的共同载体。二叉树节点的多语言定义《Hello 算法》仓库为每个语言都提供了可直接运行的节点实现。以 Python 的TreeNode类为例定义位于 en/codes/python/modules/tree_node.py供全部树章节复用其余语言的核心结构与本章文档一致可在对应语言目录下找到。Pythonclass TreeNode: Binary tree node def __init__(self, val: int): self.val: int val # Node value self.left: TreeNode | None None # Reference to left child node self.right: TreeNode | None None # Reference to right child nodeC/* Binary tree node */ struct TreeNode { int val; // Node value TreeNode *left; // Pointer to left child node TreeNode *right; // Pointer to right child node TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };Java/* Binary tree node */ class TreeNode { int val; // Node value TreeNode left; // Reference to left child node TreeNode right; // Reference to right child node TreeNode(int x) { val x; } }C#/* Binary tree node */ class TreeNode(int? x) { public int? val x; // Node value public TreeNode? left; // Reference to left child node public TreeNode? right; // Reference to right child node }Go/* Binary tree node */ type TreeNode struct { Val int Left *TreeNode Right *TreeNode } /* Constructor */ func NewTreeNode(v int) *TreeNode { return TreeNode{ Left: nil, // Pointer to left child node Right: nil, // Pointer to right child node Val: v, // Node value } }Swift/* Binary tree node */ class TreeNode { var val: Int // Node value var left: TreeNode? // Reference to left child node var right: TreeNode? // Reference to right child node init(x: Int) { val x } }JavaScript/* Binary tree node */ class TreeNode { val; // Node value left; // Pointer to left child node right; // Pointer to right child node constructor(val, left, right) { this.val val undefined ? 0 : val; this.left left undefined ? null : left; this.right right undefined ? null : right; } }TypeScript/* Binary tree node */ class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { this.val val undefined ? 0 : val; // Node value this.left left undefined ? null : left; // Reference to left child node this.right right undefined ? null : right; // Reference to right child node } }Dart/* Binary tree node */ class TreeNode { int val; // Node value TreeNode? left; // Reference to left child node TreeNode? right; // Reference to right child node TreeNode(this.val, [this.left, this.right]); }Rustuse std::rc::Rc; use std::cell::RefCell; /* Binary tree node */ struct TreeNode { val: i32, // Node value left: OptionRcRefCellTreeNode, // Reference to left child node right: OptionRcRefCellTreeNode, // Reference to right child node } impl TreeNode { /* Constructor */ fn new(val: i32) - RcRefCellSelf { Rc::new(RefCell::new(Self { val, left: None, right: None })) } }C定义见 en/codes/c/chapter_tree/binary_tree.c/* Binary tree node */ typedef struct TreeNode { int val; // Node value int height; // Node height struct TreeNode *left; // Pointer to left child node struct TreeNode *right; // Pointer to right child node } TreeNode; /* Constructor */ 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; }Kotlin/* Binary tree node */ class TreeNode(val _val: Int) { // Node value var left: TreeNode? null // Reference to left child node var right: TreeNode? null // Reference to right child node }Ruby### Binary tree node class ### class TreeNode attr_accessor :val # Node value attr_accessor :left # Reference to left child node attr_accessor :right # Reference to right child node def initialize(val) val val end end值得留意的是在内存受限的语言如 C中节点还常额外维护height字段以支持 AVL 树等高阶结构在 Rust 中节点则通过OptionRcRefCellTreeNode实现共享所有权与内部可变性这是 Rust 表达循环引用型数据结构的惯用手段。二叉树的常用术语二叉树有一套严谨且被普遍使用的术语体系图示如下根节点root node二叉树最顶层的节点没有父节点叶节点leaf node没有任何子节点的节点其两个引用都指向None边edge连接两个节点的线段表示节点之间的引用指针层level自顶向下递增根节点位于第 1 层度degree一个节点拥有的子节点数量在二叉树中度只能是 0、1 或 2二叉树高度height of tree从根节点到最远叶节点经过的边的数量节点深度depth从根节点到该节点经过的边的数量节点高度height of node从该节点到其最远叶节点经过的边的数量。概念提示一般我们约定高度和深度统计的是经过的边的条数但部分教材与题目将其定义为路径上节点的个数此时两者数值都会比边数口径大 1。阅读题面与算法描述时需先确认口径。二叉树的基本操作初始化二叉树与链表类似二叉树的初始化分两步先创建节点再建立节点间的引用指针。下面以 Python 驱动代码见 en/codes/python/chapter_tree/binary_tree.py为例构造一棵 5 节点二叉树节点 1 为根左子树挂 2-4、2-5右子树挂 3。# Initializing a binary tree # Initializing nodes n1 TreeNode(val1) n2 TreeNode(val2) n3 TreeNode(val3) n4 TreeNode(val4) n5 TreeNode(val5) # Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5C/* Initializing a binary tree */ // Initializing nodes TreeNode* n1 new TreeNode(1); TreeNode* n2 new TreeNode(2); TreeNode* n3 new TreeNode(3); TreeNode* n4 new TreeNode(4); TreeNode* n5 new TreeNode(5); // Linking references (pointers) between nodes n1-left n2; n1-right n3; n2-left n4; n2-right n5;Java完整驱动代码见 en/codes/java/chapter_tree/binary_tree.java// Initializing nodes TreeNode n1 new TreeNode(1); TreeNode n2 new TreeNode(2); TreeNode n3 new TreeNode(3); TreeNode n4 new TreeNode(4); TreeNode n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;C#/* Initializing a binary tree */ // Initializing nodes TreeNode n1 new(1); TreeNode n2 new(2); TreeNode n3 new(3); TreeNode n4 new(4); TreeNode n5 new(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Go/* Initializing a binary tree */ // Initializing nodes n1 : NewTreeNode(1) n2 : NewTreeNode(2) n3 : NewTreeNode(3) n4 : NewTreeNode(4) n5 : NewTreeNode(5) // Linking references (pointers) between nodes n1.Left n2 n1.Right n3 n2.Left n4 n2.Right n5Swift// Initializing nodes let n1 TreeNode(x: 1) let n2 TreeNode(x: 2) let n3 TreeNode(x: 3) let n4 TreeNode(x: 4) let n5 TreeNode(x: 5) // Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5JavaScript / TypeScript/* Initializing a binary tree */ // Initializing nodes let n1 new TreeNode(1), n2 new TreeNode(2), n3 new TreeNode(3), n4 new TreeNode(4), n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Dart/* Initializing a binary tree */ // Initializing nodes TreeNode n1 new TreeNode(1); TreeNode n2 new TreeNode(2); TreeNode n3 new TreeNode(3); TreeNode n4 new TreeNode(4); TreeNode n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Rust// Initializing nodes let n1 TreeNode::new(1); let n2 TreeNode::new(2); let n3 TreeNode::new(3); let n4 TreeNode::new(4); let n5 TreeNode::new(5); // Linking references (pointers) between nodes n1.borrow_mut().left Some(n2.clone()); n1.borrow_mut().right Some(n3); n2.borrow_mut().left Some(n4); n2.borrow_mut().right Some(n5);C/* Initializing a binary tree */ // Initializing nodes TreeNode *n1 newTreeNode(1); TreeNode *n2 newTreeNode(2); TreeNode *n3 newTreeNode(3); TreeNode *n4 newTreeNode(4); TreeNode *n5 newTreeNode(5); // Linking references (pointers) between nodes n1-left n2; n1-right n3; n2-left n4; n2-right n5;Kotlin// Initializing nodes val n1 TreeNode(1) val n2 TreeNode(2) val n3 TreeNode(3) val n4 TreeNode(4) val n5 TreeNode(5) // Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5Ruby# Initializing a binary tree # Initializing nodes n1 TreeNode.new(1) n2 TreeNode.new(2) n3 TreeNode.new(3) n4 TreeNode.new(4) n5 TreeNode.new(5) # Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5各语言的驱动代码在完成上述引用装配后还会调用配套的树形打印工具Python 侧为modules下的print_tree输出树的 ASCII 结构方便直观核对建树结果。插入与删除节点与链表相同二叉树的插入与删除也只需修改指针即可完成。下图演示了在节点 1 与节点 2 之间插入节点 P以及随后删除节点 P 的过程以 Python 为例核心操作只有两处指针重连# Inserting and removing nodes p TreeNode(0) # Inserting node P between n1 - n2 n1.left p p.left n2 # Removing node P n1.left n2C/* Inserting and removing nodes */ TreeNode* P new TreeNode(0); // Inserting node P between n1 and n2 n1-left P; P-left n2; // Removing node P n1-left n2;JavaTreeNode P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;C#/* Inserting and removing nodes */ TreeNode P new(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Go/* Inserting and removing nodes */ // Inserting node P between n1 and n2 p : NewTreeNode(0) n1.Left p p.Left n2 // Removing node P n1.Left n2Swiftlet P TreeNode(x: 0) // Inserting node P between n1 and n2 n1.left P P.left n2 // Removing node P n1.left n2JavaScript / TypeScript/* Inserting and removing nodes */ let P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Dart/* Inserting and removing nodes */ TreeNode P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Rustlet p TreeNode::new(0); // Inserting node P between n1 and n2 n1.borrow_mut().left Some(p.clone()); p.borrow_mut().left Some(n2.clone()); // Removing node P n1.borrow_mut().left Some(n2);C/* Inserting and removing nodes */ TreeNode *P newTreeNode(0); // Inserting node P between n1 and n2 n1-left P; P-left n2; // Removing node P n1-left n2;Kotlinval P TreeNode(0) // Inserting node P between n1 and n2 n1.left P P.left n2 // Removing node P n1.left n2Ruby# Inserting and removing nodes _p TreeNode.new(0) # Inserting node _p between n1 and n2 n1.left _p _p.left n2 # Removing node _p n1.left n2易错提醒请务必牢记——插入节点会改变二叉树原有的逻辑结构而删除节点通常意味着连同该节点整棵子树一起移除上面的例子仅摘除了叶子级节点 P故只需恢复n1.left n2。因此在实际应用中二叉树的插入与删除往往是一系列操作协调配合的结果才能得到有意义的结构如二叉搜索树、AVL 树的旋转调整。由于多数节点只持有左右孩子指针而无父指针独立删除一个带有子树的中间节点通常需要额外的子树搬运或整棵重连这是与链表删除的重要差异。二叉树的常见类型完美二叉树Perfect Binary Tree完美二叉树每一层都被完全填满。在完美二叉树中叶节点的度为 0其余所有节点的度均为 2。若树高为 $h$则总节点数为 $2^{h1} - 1$呈标准的指数规律与自然界细胞分裂的现象同构。概念提示在中文社区中Perfect Binary Tree 常被称为满二叉树与英文术语的指代并不一一对应阅读跨语言资料时需注意。完全二叉树Complete Binary Tree完全二叉树只允许最底层未被填满且底层节点必须从左到右连续填充。注意完美二叉树同时也是完全二叉树。完全二叉树是用数组紧凑存储树的前提父子节点的下标存在 $2i1$ 与 $2i2$ 的固定换算关系详情可参见数组表示二叉树。满二叉树Full Binary Tree满二叉树中除叶节点外所有节点都有两个子节点不存在度仅为 1 的节点。满二叉树不要求各层完全填满约束比完美二叉树更宽松。平衡二叉树Balanced Binary Tree平衡二叉树要求任意节点的左右子树高度之差的绝对值不超过 1。它是 AVL 树等自平衡结构的基础定义仓库的AVL 树章节即在此基础上展开旋转与平衡因子分析。二叉树的退化从完美到链表下图对比了二叉树的理想结构与退化结构当每一层都被填满时树成为完美二叉树当所有节点都偏向一侧时二叉树退化为链表。完美二叉树是理想情形能充分发挥二叉树分治divide-and-conquer的优势使查询、插入等操作的对数级复杂度成立链表是另一个极端此时所有操作退化为线性操作时间复杂度劣化到 $O(n)$。两种极端结构下叶节点数量、总节点数与高度呈现如下对照关系指标完美二叉树链表第 $i$ 层的节点数$2^{i-1}$$1$高度为 $h$ 的树的叶节点数$2^h$$1$高度为 $h$ 的树的总节点数$2^{h1} - 1$$h 1$总节点数为 $n$ 的树的高度$\log_2 (n1) - 1$$n - 1$这张表直观揭示了二叉树的核心权衡节点数固定时结构越饱满高度越低单次路径上的操作步数越少结构越偏斜高度越接近 $n$二叉树的优势便荡然无存。这也正是后续二叉搜索树追求近似平衡、AVL 树等结构引入旋转机制的根本动机。小结与延伸阅读本文覆盖了二叉树最基础也最关键的知识点节点三要素值 左右引用、父子与左右子树关系、八大常用术语根/叶/边/层/度/高度/深度、链表式建树与指针级插入删除、四类特殊二叉树以及完美二叉树与链表的数量级对照。二叉树本身更多是骨架真正产生价值的是附着其上的遍历、搜索与平衡策略建议按以下顺序继续深入本章二叉树的遍历前序/中序/后序/层序掌握 DFS 与 BFS 两种访问范式数组表示二叉树理解完全二叉树的紧凑存储与序列化规则二叉搜索树与 AVL 树见证退化问题如何通过结构约束得到根治动手运行仓库中的各语言驱动代码如 Python、Java、C并结合本章习题巩固对指针操作与术语口径的理解。【免费下载链接】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），仅供参考 二叉树入门精讲：从节点结构到退化分析的完整指南（Hello 算法）
二叉树入门精讲从节点结构到退化分析的完整指南Hello 算法【免费下载链接】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 算法》英文版「二叉树Binary Tree」一章原文档系统讲解二叉树的节点定义、父子与子树关系、常用术语、初始化与增删节点的指针操作、完美/完全/满/平衡四类特殊二叉树以及二叉树退化与最优/最坏结构的量化对比。读完本文你将能够用 Python、Java、C、C、Go、Rust 等主流语言独立搭建一棵二叉树并准确理解与运用高度、深度、度、层等核心概念。二叉树的定义祖先与后代的分治骨架与线性数据结构不同二叉树描述的是节点之间的「祖先—后代」层次关系天然体现了一种「一分为二」的分治模式。同链表一样二叉树的基本单元是节点node每个节点包含三部分一个值value存储该节点的数据一个左孩子引用/指针left指向其左子节点一个右孩子引用/指针right指向其右子节点。每个节点拥有两个引用分别指向左孩子节点left-child node与右孩子节点right-child node该节点同时被称为这两个子节点的父节点parent node。给定二叉树中某个节点后由该节点的左孩子及其下方全部节点构成的树称为该节点的左子树left subtree**右子树right subtree**同理。**在二叉树中每个非叶节点都拥有子节点因而也拥有非空子树。**例如下图中若把节点 2视作父节点则它的左、右孩子分别是节点 4和节点 5左子树由节点 4及其下方节点构成右子树由节点 5及其下方节点构成。这种一节点生两枝、两枝再分叉的结构与自然界细胞分裂的规律同构是后续二叉搜索树、AVL 树、堆与各类分治算法的共同载体。二叉树节点的多语言定义《Hello 算法》仓库为每个语言都提供了可直接运行的节点实现。以 Python 的TreeNode类为例定义位于 en/codes/python/modules/tree_node.py供全部树章节复用其余语言的核心结构与本章文档一致可在对应语言目录下找到。Pythonclass TreeNode: Binary tree node def __init__(self, val: int): self.val: int val # Node value self.left: TreeNode | None None # Reference to left child node self.right: TreeNode | None None # Reference to right child nodeC/* Binary tree node */ struct TreeNode { int val; // Node value TreeNode *left; // Pointer to left child node TreeNode *right; // Pointer to right child node TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };Java/* Binary tree node */ class TreeNode { int val; // Node value TreeNode left; // Reference to left child node TreeNode right; // Reference to right child node TreeNode(int x) { val x; } }C#/* Binary tree node */ class TreeNode(int? x) { public int? val x; // Node value public TreeNode? left; // Reference to left child node public TreeNode? right; // Reference to right child node }Go/* Binary tree node */ type TreeNode struct { Val int Left *TreeNode Right *TreeNode } /* Constructor */ func NewTreeNode(v int) *TreeNode { return TreeNode{ Left: nil, // Pointer to left child node Right: nil, // Pointer to right child node Val: v, // Node value } }Swift/* Binary tree node */ class TreeNode { var val: Int // Node value var left: TreeNode? // Reference to left child node var right: TreeNode? // Reference to right child node init(x: Int) { val x } }JavaScript/* Binary tree node */ class TreeNode { val; // Node value left; // Pointer to left child node right; // Pointer to right child node constructor(val, left, right) { this.val val undefined ? 0 : val; this.left left undefined ? null : left; this.right right undefined ? null : right; } }TypeScript/* Binary tree node */ class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { this.val val undefined ? 0 : val; // Node value this.left left undefined ? null : left; // Reference to left child node this.right right undefined ? null : right; // Reference to right child node } }Dart/* Binary tree node */ class TreeNode { int val; // Node value TreeNode? left; // Reference to left child node TreeNode? right; // Reference to right child node TreeNode(this.val, [this.left, this.right]); }Rustuse std::rc::Rc; use std::cell::RefCell; /* Binary tree node */ struct TreeNode { val: i32, // Node value left: OptionRcRefCellTreeNode, // Reference to left child node right: OptionRcRefCellTreeNode, // Reference to right child node } impl TreeNode { /* Constructor */ fn new(val: i32) - RcRefCellSelf { Rc::new(RefCell::new(Self { val, left: None, right: None })) } }C定义见 en/codes/c/chapter_tree/binary_tree.c/* Binary tree node */ typedef struct TreeNode { int val; // Node value int height; // Node height struct TreeNode *left; // Pointer to left child node struct TreeNode *right; // Pointer to right child node } TreeNode; /* Constructor */ 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; }Kotlin/* Binary tree node */ class TreeNode(val _val: Int) { // Node value var left: TreeNode? null // Reference to left child node var right: TreeNode? null // Reference to right child node }Ruby### Binary tree node class ### class TreeNode attr_accessor :val # Node value attr_accessor :left # Reference to left child node attr_accessor :right # Reference to right child node def initialize(val) val val end end值得留意的是在内存受限的语言如 C中节点还常额外维护height字段以支持 AVL 树等高阶结构在 Rust 中节点则通过OptionRcRefCellTreeNode实现共享所有权与内部可变性这是 Rust 表达循环引用型数据结构的惯用手段。二叉树的常用术语二叉树有一套严谨且被普遍使用的术语体系图示如下根节点root node二叉树最顶层的节点没有父节点叶节点leaf node没有任何子节点的节点其两个引用都指向None边edge连接两个节点的线段表示节点之间的引用指针层level自顶向下递增根节点位于第 1 层度degree一个节点拥有的子节点数量在二叉树中度只能是 0、1 或 2二叉树高度height of tree从根节点到最远叶节点经过的边的数量节点深度depth从根节点到该节点经过的边的数量节点高度height of node从该节点到其最远叶节点经过的边的数量。概念提示一般我们约定高度和深度统计的是经过的边的条数但部分教材与题目将其定义为路径上节点的个数此时两者数值都会比边数口径大 1。阅读题面与算法描述时需先确认口径。二叉树的基本操作初始化二叉树与链表类似二叉树的初始化分两步先创建节点再建立节点间的引用指针。下面以 Python 驱动代码见 en/codes/python/chapter_tree/binary_tree.py为例构造一棵 5 节点二叉树节点 1 为根左子树挂 2-4、2-5右子树挂 3。# Initializing a binary tree # Initializing nodes n1 TreeNode(val1) n2 TreeNode(val2) n3 TreeNode(val3) n4 TreeNode(val4) n5 TreeNode(val5) # Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5C/* Initializing a binary tree */ // Initializing nodes TreeNode* n1 new TreeNode(1); TreeNode* n2 new TreeNode(2); TreeNode* n3 new TreeNode(3); TreeNode* n4 new TreeNode(4); TreeNode* n5 new TreeNode(5); // Linking references (pointers) between nodes n1-left n2; n1-right n3; n2-left n4; n2-right n5;Java完整驱动代码见 en/codes/java/chapter_tree/binary_tree.java// Initializing nodes TreeNode n1 new TreeNode(1); TreeNode n2 new TreeNode(2); TreeNode n3 new TreeNode(3); TreeNode n4 new TreeNode(4); TreeNode n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;C#/* Initializing a binary tree */ // Initializing nodes TreeNode n1 new(1); TreeNode n2 new(2); TreeNode n3 new(3); TreeNode n4 new(4); TreeNode n5 new(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Go/* Initializing a binary tree */ // Initializing nodes n1 : NewTreeNode(1) n2 : NewTreeNode(2) n3 : NewTreeNode(3) n4 : NewTreeNode(4) n5 : NewTreeNode(5) // Linking references (pointers) between nodes n1.Left n2 n1.Right n3 n2.Left n4 n2.Right n5Swift// Initializing nodes let n1 TreeNode(x: 1) let n2 TreeNode(x: 2) let n3 TreeNode(x: 3) let n4 TreeNode(x: 4) let n5 TreeNode(x: 5) // Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5JavaScript / TypeScript/* Initializing a binary tree */ // Initializing nodes let n1 new TreeNode(1), n2 new TreeNode(2), n3 new TreeNode(3), n4 new TreeNode(4), n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Dart/* Initializing a binary tree */ // Initializing nodes TreeNode n1 new TreeNode(1); TreeNode n2 new TreeNode(2); TreeNode n3 new TreeNode(3); TreeNode n4 new TreeNode(4); TreeNode n5 new TreeNode(5); // Linking references (pointers) between nodes n1.left n2; n1.right n3; n2.left n4; n2.right n5;Rust// Initializing nodes let n1 TreeNode::new(1); let n2 TreeNode::new(2); let n3 TreeNode::new(3); let n4 TreeNode::new(4); let n5 TreeNode::new(5); // Linking references (pointers) between nodes n1.borrow_mut().left Some(n2.clone()); n1.borrow_mut().right Some(n3); n2.borrow_mut().left Some(n4); n2.borrow_mut().right Some(n5);C/* Initializing a binary tree */ // Initializing nodes TreeNode *n1 newTreeNode(1); TreeNode *n2 newTreeNode(2); TreeNode *n3 newTreeNode(3); TreeNode *n4 newTreeNode(4); TreeNode *n5 newTreeNode(5); // Linking references (pointers) between nodes n1-left n2; n1-right n3; n2-left n4; n2-right n5;Kotlin// Initializing nodes val n1 TreeNode(1) val n2 TreeNode(2) val n3 TreeNode(3) val n4 TreeNode(4) val n5 TreeNode(5) // Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5Ruby# Initializing a binary tree # Initializing nodes n1 TreeNode.new(1) n2 TreeNode.new(2) n3 TreeNode.new(3) n4 TreeNode.new(4) n5 TreeNode.new(5) # Linking references (pointers) between nodes n1.left n2 n1.right n3 n2.left n4 n2.right n5各语言的驱动代码在完成上述引用装配后还会调用配套的树形打印工具Python 侧为modules下的print_tree输出树的 ASCII 结构方便直观核对建树结果。插入与删除节点与链表相同二叉树的插入与删除也只需修改指针即可完成。下图演示了在节点 1 与节点 2 之间插入节点 P以及随后删除节点 P 的过程以 Python 为例核心操作只有两处指针重连# Inserting and removing nodes p TreeNode(0) # Inserting node P between n1 - n2 n1.left p p.left n2 # Removing node P n1.left n2C/* Inserting and removing nodes */ TreeNode* P new TreeNode(0); // Inserting node P between n1 and n2 n1-left P; P-left n2; // Removing node P n1-left n2;JavaTreeNode P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;C#/* Inserting and removing nodes */ TreeNode P new(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Go/* Inserting and removing nodes */ // Inserting node P between n1 and n2 p : NewTreeNode(0) n1.Left p p.Left n2 // Removing node P n1.Left n2Swiftlet P TreeNode(x: 0) // Inserting node P between n1 and n2 n1.left P P.left n2 // Removing node P n1.left n2JavaScript / TypeScript/* Inserting and removing nodes */ let P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Dart/* Inserting and removing nodes */ TreeNode P new TreeNode(0); // Inserting node P between n1 and n2 n1.left P; P.left n2; // Removing node P n1.left n2;Rustlet p TreeNode::new(0); // Inserting node P between n1 and n2 n1.borrow_mut().left Some(p.clone()); p.borrow_mut().left Some(n2.clone()); // Removing node P n1.borrow_mut().left Some(n2);C/* Inserting and removing nodes */ TreeNode *P newTreeNode(0); // Inserting node P between n1 and n2 n1-left P; P-left n2; // Removing node P n1-left n2;Kotlinval P TreeNode(0) // Inserting node P between n1 and n2 n1.left P P.left n2 // Removing node P n1.left n2Ruby# Inserting and removing nodes _p TreeNode.new(0) # Inserting node _p between n1 and n2 n1.left _p _p.left n2 # Removing node _p n1.left n2易错提醒请务必牢记——插入节点会改变二叉树原有的逻辑结构而删除节点通常意味着连同该节点整棵子树一起移除上面的例子仅摘除了叶子级节点 P故只需恢复n1.left n2。因此在实际应用中二叉树的插入与删除往往是一系列操作协调配合的结果才能得到有意义的结构如二叉搜索树、AVL 树的旋转调整。由于多数节点只持有左右孩子指针而无父指针独立删除一个带有子树的中间节点通常需要额外的子树搬运或整棵重连这是与链表删除的重要差异。二叉树的常见类型完美二叉树Perfect Binary Tree完美二叉树每一层都被完全填满。在完美二叉树中叶节点的度为 0其余所有节点的度均为 2。若树高为 $h$则总节点数为 $2^{h1} - 1$呈标准的指数规律与自然界细胞分裂的现象同构。概念提示在中文社区中Perfect Binary Tree 常被称为满二叉树与英文术语的指代并不一一对应阅读跨语言资料时需注意。完全二叉树Complete Binary Tree完全二叉树只允许最底层未被填满且底层节点必须从左到右连续填充。注意完美二叉树同时也是完全二叉树。完全二叉树是用数组紧凑存储树的前提父子节点的下标存在 $2i1$ 与 $2i2$ 的固定换算关系详情可参见数组表示二叉树。满二叉树Full Binary Tree满二叉树中除叶节点外所有节点都有两个子节点不存在度仅为 1 的节点。满二叉树不要求各层完全填满约束比完美二叉树更宽松。平衡二叉树Balanced Binary Tree平衡二叉树要求任意节点的左右子树高度之差的绝对值不超过 1。它是 AVL 树等自平衡结构的基础定义仓库的AVL 树章节即在此基础上展开旋转与平衡因子分析。二叉树的退化从完美到链表下图对比了二叉树的理想结构与退化结构当每一层都被填满时树成为完美二叉树当所有节点都偏向一侧时二叉树退化为链表。完美二叉树是理想情形能充分发挥二叉树分治divide-and-conquer的优势使查询、插入等操作的对数级复杂度成立链表是另一个极端此时所有操作退化为线性操作时间复杂度劣化到 $O(n)$。两种极端结构下叶节点数量、总节点数与高度呈现如下对照关系指标完美二叉树链表第 $i$ 层的节点数$2^{i-1}$$1$高度为 $h$ 的树的叶节点数$2^h$$1$高度为 $h$ 的树的总节点数$2^{h1} - 1$$h 1$总节点数为 $n$ 的树的高度$\log_2 (n1) - 1$$n - 1$这张表直观揭示了二叉树的核心权衡节点数固定时结构越饱满高度越低单次路径上的操作步数越少结构越偏斜高度越接近 $n$二叉树的优势便荡然无存。这也正是后续二叉搜索树追求近似平衡、AVL 树等结构引入旋转机制的根本动机。小结与延伸阅读本文覆盖了二叉树最基础也最关键的知识点节点三要素值 左右引用、父子与左右子树关系、八大常用术语根/叶/边/层/度/高度/深度、链表式建树与指针级插入删除、四类特殊二叉树以及完美二叉树与链表的数量级对照。二叉树本身更多是骨架真正产生价值的是附着其上的遍历、搜索与平衡策略建议按以下顺序继续深入本章二叉树的遍历前序/中序/后序/层序掌握 DFS 与 BFS 两种访问范式数组表示二叉树理解完全二叉树的紧凑存储与序列化规则二叉搜索树与 AVL 树见证退化问题如何通过结构约束得到根治动手运行仓库中的各语言驱动代码如 Python、Java、C并结合本章习题巩固对指针操作与术语口径的理解。【免费下载链接】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），仅供参考