二叉树：数据结构中的核心概念与基础-港品优选

什么是树？

在正式学习二叉树之前，我们先来认识一下更一般的概念——树（Tree）。

树的定义

树是一种非线性的数据结构，它由n（n ≥ 0）个节点和连接节点之间的**边（Edge）**组成，并且满足以下两个条件：

有且仅有一个根节点（Root），它是整棵树的起点，没有父节点
除根节点外，其余每个节点有且仅有一个父节点，且可以通过唯一的路径从根节点到达

当 n = 0 时，称为空树。

树的基本术语

节点（Node）：树中的基本单元，存储数据
边（Edge）：连接父节点与子节点的线段，表示节点间的隶属关系
根节点（Root）：整棵树的顶端节点，没有父节点
叶子节点（Leaf）：没有子节点的节点，也叫终端节点
父节点（Parent）：某个节点的直接上级节点
子节点（Child）：某个节点的直接下级节点
兄弟节点（Sibling）：拥有同一个父节点的节点
祖先节点（Ancestor）：从根节点到某节点路径上的所有节点
后代节点（Descendant）：某节点子树中的所有节点
深度（Depth）：从根节点到该节点的路径长度（根节点深度为 0 或 1，视定义而定）
高度（Height）：从该节点到最远叶子节点的路径长度
度（Degree）：一个节点拥有的子节点个数
层（Level）：根节点在第 1 层，其子节点在第 2 层，依此类推

树的性质

节点数 = 边数 + 1：树中 n 个节点恰好有 n-1 条边
或者说成：节点数=所有节点的度之和+1
m叉树中第 i 层上最多有 m^i-1个节点（i>=1）：m叉树指每个节点最多有m个孩子，极端场景下⾼度为h的m叉树叶⼦结点都在第h层，每个分⽀结点均有m个孩⼦，每层都是满的，假设层数是i，则每层结点数为 mi−1 ，第1⾄h层的结点数是⼀个以m为公⽐的等⽐数列。

3.高度为h的m叉树最多有（m^h-1） / （m-1）个节点
3.连通且无环：任意两个节点之间有且仅有一条路径，树中不存在回路
5.有向性：边具有方向性，从父节点指向子节点
6.层次性：树天然具有层级结构，适合表达具有从属关系的数据

树的分类

根据节点的子节点数量，树可以分为：

二叉树（Binary Tree）：每个节点最多有两个子节点，是最常用的一种树
多叉树（Multi-way Tree）：每个节点可以有多个子节点，如 B 树、Trie 树等

下面这张图展示了一棵典型的树结构：

A ← 根节点（第 1 层） / | \ B C D ← 第 2 层 / \ | E F G ← 第 3 层（叶子节点：E、F、G）

在这棵树中：A 是根节点；B、C、D 是 A 的子节点，互为兄弟节点；E、F 是 B 的子节点；G 是 D 的子节点；E、F、G 都是叶子节点。

再举一个例子：

理解了树的基本概念之后，我们再来看它的特例——二叉树，就会轻松很多。

1. 什么是二叉树？

二叉树（Binary Tree）是计算机科学中最基础、最重要的数据结构之一。它是一种树形结构，其中每个节点最多有两个子节点（也可以称为子树），通常称为左子节点和右子节点。

1.1 基本定义（以下部分）

节点（Node）：树中的基本单元，包含数据和指向子节点的指针
根节点（Root）：树的顶端节点，没有父节点
叶子节点（Leaf）：没有子节点的节点
深度（Depth）：从根节点到该节点的路径长度
高度（Height）：从该节点到最远叶子节点的路径长度

补充：节点间关系的描述（了解就行）

关系示例：
考虑以下二叉树：

A / \ B C / \ \ D E F

A是B和C的父节点，B和C是A的子节点
B和C是兄弟节点
A是D、E、F的祖先节点
D、E、F是A的后代节点
B是D和E的父节点，D和E是兄弟节点
以B为根的子树包含B、D、E三个节点

上述概念不用刻意去背，平常知道是什么就可以

2. 二叉树的基本性质

2.1 结构特性

每个节点最多有两个子节点
子树有左右之分，顺序不能颠倒
第 i 层最多有 2^(i-1)个节点
深度为 k 的二叉树最多有 2^k- 1 个节点
对于任意一个二叉树，如果度为2的节点数为n2，度为0的节点数为n0，则n0 = n2 +1
可以自己画个二叉树现推规律，也可以用前面的性质推导（度为1则叫n1）：节点数m = n1 + 2*n2 + 1（度之和+1）=n0 + n1 +n2化简就能得到
具有n个节点的完全二叉树的高度为[log 2 n]+1，[ ]为向下取整，可以由2^h-1< n < 2^h两边同时取对数得到

补充：二叉树具有递归性质，任何一个二叉树都可以分成左子树与右子树与根，非空的子树亦可以分为左子树右子树与根…

2.2 特殊类型

满二叉树（Full Binary Tree）：每个节点都有 0 或 2 个子节点，套用等比数列前n项和公式可以得出高度为h的满二叉树总结点为2^h-1个
完全二叉树（Complete Binary Tree）：除最后一层外，其他层都是满的，且最后一层节点尽量靠左，完全⼆叉树的叶⼦⼀定只出现在最后两层，且度为1的结点最多有1个，剩下的结点都是度为0和度
为2。
完美二叉树（Perfect Binary Tree）：所有叶子节点都在同一层，且每个非叶子节点都有两个子节点

3. 二叉树的存储方式

3.1 链式存储

最常用的存储方式，每个节点包含：

数据域
左子节点指针
右子节点指针

有些情况下需要记录父节点的地址，比如红黑树

typedefstructTreeNode{intval;// 节点值structTreeNode*left;// 左子节点structTreeNode*right;// 右子节点}TreeNode;

3.2 顺序存储（数组）

对于完全二叉树，可以使用数组存储：

根节点存储在索引 1 的位置
节点 i 的左子节点在 2*i
节点 i 的右子节点在 2*i + 1
节点 i 的父节点在 i//2
如图：

补充：

顺序存储里，节点权不是靠"存地址"连起来的，而是靠"下标之间的数学关系"连起来的。
使用完全二叉树可以避免空间浪费，并且因为完全二叉树有个完美性质：按层从上到下、从左到右编上号，这个编号本身就隐含了父子关系
数组的下标从0开始，如果想美观，可以舍弃一个空间，如果不舍弃，公式是：
左孩子：2i + 1
右孩子：2i + 2
父节点：(i - 1) / 2

从0开始是比较常用的，可以记住公式，也可以画个简单的二叉树推到一下

4.堆

堆（Heap）是一种特殊的完全二叉树，常用于实现优先队列（Priority Queue）。它满足以下两个条件：

结构性质：堆是一棵完全二叉树，即除最后一层外，其他层都是满的，且最后一层节点尽量靠左。
堆序性质：根据父节点与子节点的大小关系，堆分为两种：
- 大根堆（Max Heap）：父节点值 ≥ 子节点值，堆顶是最大值
- 小根堆（Min Heap）：父节点值 ≤ 子节点值，堆顶是最小值

对兄弟节点之间的大小没有要求

由于堆是完全二叉树，通常使用数组进行存储，下标关系与 3.2 节一致（这里采用从 1 开始的下标，便于理解）：

节点 i 的左子节点在2*i
节点 i 的右子节点在2*i + 1
节点 i 的父节点在i//2

4.1 堆的存储结构

用数组存储堆时，数组下标从 1 开始，heap[0]可以存放堆的大小或闲置不用。例如下面这个大根堆：

90 / \ 80 70 / \ / \ 60 50 40 30

对应的数组为：[_, 90, 80, 70, 60, 50, 40, 30]（_表示下标 0 闲置）。

4.2 堆的插入操作（上浮 sift up）

插入操作的基本思路：

将新元素添加到数组末尾（即完全二叉树的最后一个位置）。
从该位置开始上浮（sift up）：不断与父节点比较，若违反堆序性质（大根堆中新元素大于父节点），则交换，直到满足堆序或到达根节点。

时间复杂度为O(log n)。

补充：

相比于冒泡的O(n²)，堆排序的效率很高，这也是堆排序出现的原因之一
上浮所需要的最坏情况就是进行该二叉树高度次数的比较，由上面的知识2.1.6可得到时间复杂度

// 大根堆的插入voidheap_insert(intheap[],int*size,intval){inti=++(*size);// 新元素放在末尾heap[i]=val;// 上浮：与父节点比较并交换while(i>1&&heap[i]>heap[i/2]){inttmp=heap[i];heap[i]=heap[i/2];heap[i/2]=tmp;i=i/2;}}

4.3 堆的删除操作（下沉 sift down）

堆的删除通常指删除堆顶元素（大根堆的最大值或小根堆的最小值）。基本思路：

用数组最后一个元素覆盖堆顶元素，并将堆的大小减 1。
从堆顶开始下沉（sift down）：不断与较大的子节点（大根堆）比较，若违反堆序性质则交换，直到满足堆序或到达叶子节点。

时间复杂度为O(log n)。

// 大根堆的删除（删除堆顶）voidheap_delete(intheap[],int*size){if(*size==0){return;}heap[1]=heap[*size];// 用最后一个元素覆盖堆顶(*size)--;inti=1;// 下沉：与较大的子节点比较并交换while(2*i<=*size){intchild=2*i;// 左子节点// 若右子节点存在且更大，则选择右子节点if(child+1<=*size&&heap[child+1]>heap[child]){child++;}if(heap[i]>=heap[child]){break;// 已满足堆序，停止}inttmp=heap[i];heap[i]=heap[child];heap[child]=tmp;i=child;}}

4.4 堆的建堆操作

给定一个无序数组，可以通过自底向上的下沉在O(n)时间内将其调整为堆：

// 对下标 i 执行下沉操作voidsift_down(intheap[],intn,inti){while(2*i<=n){intchild=2*i;if(child+1<=n&&heap[child+1]>heap[child]){child++;}if(heap[i]>=heap[child]){break;}inttmp=heap[i];heap[i]=heap[child];heap[child]=tmp;i=child;}}// 建堆：从最后一个非叶子节点开始，自底向上下沉voidbuild_heap(intheap[],intn){for(inti=n/2;i>=1;i--){sift_down(heap,n,i);}}

4.5 堆的完整示例

下面是一个完整的大根堆示例，包含插入、删除和建堆操作：

#include<stdio.h>#defineMAX_SIZE100intheap[MAX_SIZE];intsize=0;// 插入voidinsert(intval){inti=++size;heap[i]=val;while(i>1&&heap[i]>heap[i/2]){inttmp=heap[i];heap[i]=heap[i/2];heap[i/2]=tmp;i=i/2;}}// 删除堆顶voiddelete_top(){if(size==0){return;}heap[1]=heap[size--];inti=1;while(2*i<=size){intchild=2*i;if(child+1<=size&&heap[child+1]>heap[child]){child++;}if(heap[i]>=heap[child]){break;}inttmp=heap[i];heap[i]=heap[child];heap[child]=tmp;i=child;}}// 打印堆voidprint_heap(){for(inti=1;i<=size;i++){printf("%d ",heap[i]);}printf("\n");}intmain(){// 依次插入元素insert(50);insert(30);insert(70);insert(20);insert(60);insert(90);printf("插入后的堆：");print_heap();// 输出：90 60 70 20 30 50// 删除堆顶delete_top();printf("删除堆顶后的堆：");print_heap();// 输出：70 60 50 20 30return0;}

4.6 堆的应用

优先队列：堆是实现优先队列最常用的数据结构，插入和删除堆顶均为 O(log n)。
堆排序（Heap Sort）：利用堆的性质，反复取出堆顶元素即可完成排序，时间复杂度为 O(n log n)。
Top K 问题：在海量数据中求最大/最小的 K 个元素，用大小为 K 的堆即可高效解决。
Dijkstra 算法：求单源最短路径时，用小根堆优化取最小距离节点的过程。

4. 二叉树的遍历方式

遍历是二叉树操作的基础，主要有四种方式：

4.1 前序遍历（Pre-order）

访问顺序：根 → 左 → 右

voidpreorder(TreeNode*root){if(root==NULL){return;}printf("%d ",root->val);// 访问根节点preorder(root->left);// 遍历左子树preorder(root->right);// 遍历右子树}

4.2 中序遍历（In-order）

访问顺序：左 → 根 → 右

voidinorder(TreeNode*root){if(root==NULL){return;}inorder(root->left);// 遍历左子树printf("%d ",root->val);// 访问根节点inorder(root->right);// 遍历右子树}

4.3 后序遍历（Post-order）

访问顺序：左 → 右 → 根

voidpostorder(TreeNode*root){if(root==NULL){return;}postorder(root->left);// 遍历左子树postorder(root->right);// 遍历右子树printf("%d ",root->val);// 访问根节点}

4.4 层序遍历（Level-order）

按层次从上到下、从左到右访问

#include<stdio.h>#include<stdlib.h>voidlevelorder(TreeNode*root){if(root==NULL){return;}// 用数组模拟队列TreeNode*queue[1000];intfront=0,rear=0;queue[rear++]=root;while(front<rear){TreeNode*node=queue[front++];printf("%d ",node->val);if(node->left){queue[rear++]=node->left;}if(node->right){queue[rear++]=node->right;}}}

5. 二叉树的应用场景

5.1 搜索结构

二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值
平衡二叉树（AVL树）：保持左右子树高度差不超过 1
红黑树：自平衡二叉搜索树，广泛应用于各种库中

5.2 表达式树

用于表示算术表达式：

叶子节点：操作数
内部节点：运算符

5.3 哈夫曼树

用于数据压缩，频率高的字符使用短编码

6. 二叉树的常见操作

6.1 查找节点

deffind_node(root,target):ifnotroot:returnNoneifroot.val==target:returnroot left_result=find_node(root.left,target)ifleft_result:returnleft_resultreturnfind_node(root.right,target)

6.2 计算节点数

defcount_nodes(root):ifnotroot:return0return1+count_nodes(root.left)+count_nodes(root.right)

6.3 计算树的高度

deftree_height(root):ifnotroot:return0return1+max(tree_height(root.left),tree_height(root.right))

6.4 判断是否平衡

defis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=(left_balancedandright_balancedandabs(left_height-right_height)<=1)returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]

7. 学习建议与进阶方向

7.1 学习路线建议

掌握基础概念：理解节点、边、深度、高度等术语
熟练四种遍历：能够手写递归和非递归实现
理解特殊二叉树：BST、AVL、堆等变体的特性
解决经典问题：如求深度、判断对称、最近公共祖先等

7.2 经典练习题

二叉树的最大深度
对称二叉树的判断
二叉树的最近公共祖先
二叉树的直径
路径总和问题

7.3 进阶学习

多叉树：每个节点可以有多个子节点
B树/B+树：用于数据库索引
Trie树：用于字符串检索
线段树：用于区间查询

8. 总结

二叉树作为数据结构的基础，具有以下特点：

结构简单：每个节点最多两个子节点，易于理解和实现
操作高效：大多数操作的时间复杂度为 O(log n)
应用广泛：从基础算法到系统设计都有重要应用
扩展性强：衍生出多种变体满足不同需求

掌握二叉树不仅有助于理解更复杂的数据结构，也是算法面试中的必备技能。建议通过实际编码练习，加深对二叉树各种操作的理解。

学习二叉树最好的方式就是动手实现。从简单的节点类开始，逐步实现遍历、查找、插入等操作，再尝试解决一些经典算法问题。

企业官网建设流程全解析