☰

企业官网建设流程全解析

首页 / 建站日记 / 企业官网建设流程全解析
二叉树入门精讲：从节点结构到退化分析的完整指南（Hello 算法）
2026/11/1 1:50:41 网站建设 项目流程

二叉树入门精讲：从节点结构到退化分析的完整指南（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，供全部树章节复用；其余语言的核心结构与本章文档一致，可在对应语言目录下找到。

Python

class 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 node

C++

/* 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]); }

Rust

use std::rc::Rc; use std::cell::RefCell; /* Binary tree node */ struct TreeNode { val: i32, // Node value left: Option<Rc<RefCell<TreeNode>>>, // Reference to left child node right: Option<Rc<RefCell<TreeNode>>>, // Reference to right child node } impl TreeNode { /* Constructor */ fn new(val: i32) -> Rc<RefCell<Self>> { 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 中，节点则通过Option<Rc<RefCell<TreeNode>>>实现共享所有权与内部可变性，这是 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(val=1) n2 = TreeNode(val=2) n3 = TreeNode(val=3) n4 = TreeNode(val=4) n5 = TreeNode(val=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 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 = n5

Swift

// 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 = n5

JavaScript / 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 = n5

Ruby

# 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 = n2

C++

/* 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;

Java

TreeNode 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 = n2

Swift

let P = TreeNode(x: 0) // Inserting node P between n1 and n2 n1.left = P P.left = n2 // Removing node P n1.left = n2

JavaScript / 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;

Rust

let 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;

Kotlin

val P = TreeNode(0) // Inserting node P between n1 and n2 n1.left = P P.left = n2 // Removing node P n1.left = n2

Ruby

# 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^{h+1} - 1$，呈标准的指数规律，与自然界细胞分裂的现象同构。

概念提示：在中文社区中，Perfect Binary Tree 常被称为"满二叉树"，与英文术语的指代并不一一对应，阅读跨语言资料时需注意。

完全二叉树（Complete Binary Tree）

完全二叉树只允许最底层未被填满，且底层节点必须从左到右连续填充。注意：完美二叉树同时也是完全二叉树。完全二叉树是"用数组紧凑存储树"的前提（父子节点的下标存在 $2i+1$ 与 $2i+2$ 的固定换算关系），详情可参见数组表示二叉树。

满二叉树（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^{h+1} - 1$$h + 1$
总节点数为 $n$ 的树的高度$\log_2 (n+1) - 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），仅供参考

标签： 网站建设 企业官网 项目流程 UI设计 前端开发

热门文章

文章分类

标签云

网站建设 响应式设计 用户体验 SEO优化 前端开发 小程序 电商平台 性能优化

相关文章

您可能感兴趣的其他内容

OpenCV samples/dnn 深度学习推理示例指南：模型动物园、models.yml 预处理参数与模型权重下载实战
2026/11/1 1:49:51 网站建设

OpenCV samples/dnn 深度学习推理示例指南：模型动物园、models.yml 预处理参数与模型权重下载实战

OpenCV samples/dnn 深度学习推理示例指南&#xff1a;模型动物园、models.yml 预处理参数与模型权重下载实战 【免费下载链接】opencv Open Source Computer Vision Library 项目地址: https://gitcode.com/GitHub_Trending/opencv31/opencv OpenCV 自 3.x 起内置了高性…...

阅读更多 →
用 AutoGen 0.4 .NET 构建带状态持久化的事件驱动 Agent：HelloAgentState 实战解析
2026/10/26 7:52:21 网站建设

用 AutoGen 0.4 .NET 构建带状态持久化的事件驱动 Agent：HelloAgentState 实战解析

用 AutoGen 0.4 .NET 构建带状态持久化的事件驱动 Agent&#xff1a;HelloAgentState 实战解析 【免费下载链接】autogen A programming framework for agentic AI 项目地址: https://gitcode.com/GitHub_Trending/au/autogen 事件驱动是 Agentic AI 应用的核心运行模式…...

阅读更多 →
STM32F103C8T6驱动ILI9341 TFT LCD完整教程与调试指南
2026/10/26 7:52:23 网站建设

STM32F103C8T6驱动ILI9341 TFT LCD完整教程与调试指南

简介&#xff1a;面向STM32入门者与嵌入式开发者的ILI9341液晶显示工程&#xff0c;基于STM32F103C8T6最小系统板和2.8寸TFT LCD模块&#xff0c;重点演示如何在无FSMC的48脚芯片上用普通GPIO模拟总线&#xff0c;实现16位并口TFT驱动&#xff0c;可直接迁移到类似MCU平台&…...

阅读更多 →

需要专业的网站建设服务？

联系我们获取免费的网站建设咨询和方案报价，让我们帮助您实现业务目标

立即咨询