-
第6章 树的基本概念与二叉树
第6章 树的基本概念与二叉树
6.1 树的基本概念
6.1.1 树的定义
树是一种非线性数据结构，由n（n≥0）个节点组成的有限集合。当n=0时，称为空树；当n>0时，集合中存在唯一的一个称为根（Root） 的节点，其余节点可分为m（m≥0）个互不相交的有限子集，每个子集本身又是一棵树，称为根的子树（Subtree）。
树与线性结构的本质区别：
线性结构（如数组、链表）中，每个元素只有一个直接前驱和一个直接后继（除首尾元素），呈“一对一”关系；
树结构中，根节点无直接前驱，其他节点有且仅有一个直接前驱（父节点），但可有多个直接后继（子节点），呈“一对多”关系。
6.1.2 树的基本术语
以下术语基于图6-1所示的树结构（以根节点A为例）进行说明：
A
/ |
B C D
/ /
E F G H
/
I J
图6-1 树的结构示例
1.
节点（Node）：树的基本单元，包含数据及指向子树的引用。如节点A、B、C等。
2.
o节点的度（Degree）：节点拥有的子树数量（即直接后继节点数）。如A的度为3（子树B、C、D），B的度为2（子树E、F），E的度为0。
o叶子节点（Leaf Node）：度为0的节点（无子女）。如E、I、J、C、G、H。
o分支节点（Branch Node）：度不为0的节点。如A、B、D、F。
3.
节点间关系：
4.
o父节点（Parent）：若节点x有子树，则x是子树根节点的父节点。如A是B、C、D的父节点，B是E、F的父节点。
o子节点（Child）：父节点的直接后继。如B、C、D是A的子节点，E、F是B的子节点。
o兄弟节点（Sibling）：同一父节点的子节点互称兄弟。如B、C、D是兄弟，E、F是兄弟。
o祖先/子孙：从根到节点的路径上所有节点为该节点的祖先（不含自身）；节点的所有子树节点为其子孙。如A、B是F的祖先，F、I、J是B的子孙。
5.
树的整体属性：
6.
o层次（Level）：从根开始定义，根为第1层，其子节点为第2层，以此类推。如A在第1层，B、C、D在第2层，E、F、G、H在第3层。
o深度（Depth）：从根到节点的路径长度（即节点所在层次）。如节点F的深度为3，节点J的深度为4。
o高度（Height）：从节点到最远叶子节点的路径长度（即该节点为根的子树的最大深度）。如树的高度为4（根A到叶子I/J的路径长度），节点F的高度为2（到叶子I/J的路径长度）。
o路径（Path）：从某节点到另一节点的连续节点序列（仅允许从父节点到子节点）。如A到J的路径为A→B→F→J，路径长度为3（边数=节点数-1）。
o森林（Forest）：m（m≥0）棵互不相交的树的集合。如将图6-1的根节点A删除，其子树B、C、D构成一个森林。
6.2 二叉树的定义与特性
6.2.1 二叉树的定义
二叉树（Binary Tree） 是一种特殊的树结构，每个节点最多有两棵子树，且子树有明确的左右顺序（左子树、右子树）。即使某节点只有一棵子树，也需区分左/右子树（有序性）。
与普通树的区别：
普通树的节点度无限制，二叉树节点度≤2；
普通树的子树无序，二叉树的子树有序（左右子树不能互换）。
6.2.2 二叉树的特殊形态
1.
满二叉树（Full Binary Tree）：
深度为k的二叉树，第i层（1≤i≤k）有2^(i-1)个节点（即每层节点数达到最大值），且所有叶子节点均在第k层。
2.
例如，深度为3的满二叉树有1+2+4=7个节点，叶子节点为第3层的4个节点。
3.
4.
完全二叉树（Complete Binary Tree）：
深度为k的二叉树，前k-1层为满二叉树，第k层的节点从左至右连续排列（无空位置）。
5.
满二叉树是完全二叉树的特例，但完全二叉树不一定是满二叉树。例如，深度为3的完全二叉树，第3层可有1~4个节点，但必须从左到右排列（不能出现“左空右有”的情况）。
6.
6.2.3 二叉树的重要性质
以下性质中，“深度”默认从1开始计数（根节点为第1层）。
性质1：第i层最多有2^(i-1)个节点（i≥1）。
证明：第1层（i=1）最多1=20个节点；第2层最多2=21个节点；第3层最多4=22个节点……归纳可得第i层最多2(i-1)个节点。
性质2：深度为k的二叉树最多有2^k -1个节点（k≥1）。
证明：由性质1，各层节点数之和为2^0 + 2^1 + ... + 2^(k-1) = 2^k -1（等比数列求和）。
性质3：对于任意二叉树，若叶子节点数为n0，度为2的节点数为n2，则n0 = n2 + 1。
证明：设总节点数为n，度为1的节点数为n1。则：
① n = n0 + n1 + n2（节点按度分类求和）；
② 树的边数 = n-1（n个节点有n-1条边）；
③ 边数 = n1×1 + n2×2（度为1的节点贡献1条边，度为2的节点贡献2条边，叶子节点贡献0条边）；
联立②③得n-1 = n1 + 2n2，代入①得n0 + n1 + n2 -1 = n1 + 2n2，化简得n0 = n2 + 1。
性质4：具有n个节点的完全二叉树的深度为⌊log2 n⌋ + 1（⌊x⌋表示向下取整）。
例如，n=7时，log2 7≈2.8，⌊2.8⌋+1=3（深度为3的满二叉树）；n=8时，log2 8=3，⌊3⌋+1=4（深度为4的完全二叉树）。
性质5：对完全二叉树的节点按层序编号（从1开始），则对任意节点i（1≤i≤n）：
若i=1，则i为根节点，无父节点；
若i>1，则父节点为⌊i/2⌋；
左子节点为2i（若2i≤n），否则无左子节点；
右子节点为2i+1（若2i+1≤n），否则无右子节点。
例如，图6-2的完全二叉树（n=8）中，节点5的父节点为⌊5/2⌋=2，左子节点2×5=10（>8，无），右子节点2×5+1=11（>8，无）：
1
/
2 3
/ /
4 5 6 7
/
8
图6-2 完全二叉树的节点编号
6.3 二叉树的存储结构
6.3.1 顺序存储结构
实现方式：用数组（列表）存储节点，按完全二叉树的层序编号规则分配索引（根节点存于索引1，而非0，以适配性质5的编号公式）。
若节点i的左子节点存在（2i≤n），则存储于索引2i；
若节点i的右子节点存在（2i+1≤n），则存储于索引2i+1；
非完全二叉树需用特殊值（如None）填充空节点位置，可能导致空间浪费。
示例：图6-2的完全二叉树顺序存储为：
[None, 1, 2, 3, 4, 5, 6, 7, 8]（索引0闲置，索引18对应节点18）。
适用场景：完全二叉树（无空间浪费），如堆排序中的“堆”结构。
6.3.2 链式存储结构（二叉链表）
实现方式：每个节点用链表存储，包含3个域：
数据域（val）：存储节点值；
左指针域（left）：指向左子树的根节点；
右指针域（right）：指向右子树的根节点。
节点结构定义（Python）：
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val # 数据域
self.left = left # 左子树指针
self.right = right # 右子树指针
示例：图6-2的完全二叉树链式存储结构如图6-3所示：
节点1: val=1, left=节点2, right=节点3
节点2: val=2, left=节点4, right=节点5
节点3: val=3, left=节点6, right=节点7
节点4: val=4, left=节点8, right=None
节点5: val=5, left=None, right=None
节点6: val=6, left=None, right=None
节点7: val=7, left=None, right=None
节点8: val=8, left=None, right=None
图6-3 二叉链表存储示例
适用场景：所有二叉树（尤其是非完全二叉树，无空间浪费），是二叉树最常用的存储方式。
6.4 二叉树的遍历算法
遍历（Traversal） 是指按某种规则访问树中所有节点，且每个节点仅访问一次的过程。二叉树的遍历核心是将“非线性结构”转化为“线性序列”，常用遍历方式分为深度优先遍历（前序、中序、后序）和广度优先遍历（层序）。
6.4.1 深度优先遍历（DFS）
深度优先遍历从根节点出发，优先沿左/右子树深入，直至叶子节点，再回溯访问未遍历的节点。根据根节点、左子树、右子树的访问顺序，分为以下三种：
（1）前序遍历（Preorder Traversal）
规则：根节点 → 左子树 → 右子树（根左右）。
示例：对图6-3的二叉树，前序遍历序列为：1 → 2 → 4 → 8 → 5 → 3 → 6 → 7。
递归实现
递归是遍历二叉树最直观的方式，利用函数调用栈模拟回溯过程：
python
def preorder_recursive(root: TreeNode) -> list[int]:
"""前序遍历（递归），返回节点值序列"""
res = []
def dfs(node):
if node:
res.append(node.val) # 访问根节点
dfs(node.left) # 递归遍历左子树
dfs(node.right) # 递归遍历右子树
dfs(root)
return res
非递归实现
递归本质依赖系统栈，非递归实现需手动用栈模拟：
1.根节点入栈；
2.栈非空时，弹出栈顶节点，访问其值；
3.先将右子节点入栈，再将左子节点入栈（因栈是LIFO，保证左子树先于右子树访问）；
4.重复步骤2~3，直至栈空。
python
def preorder_iterative(root: TreeNode) -> list[int]:
"""前序遍历（非递归），返回节点值序列"""
res = []
if not root:
return res
stack = [root]
while stack:
node = stack.pop()
res.append(node.val) # 访问根节点
if node.right: # 右子节点先入栈（后访问）
stack.append(node.right)
if node.left: # 左子节点后入栈（先访问）
stack.append(node.left)
return res
（2）中序遍历（Inorder Traversal）
规则：左子树 → 根节点 → 右子树（左根右）。
示例：对图6-3的二叉树，中序遍历序列为：8 → 4 → 2 → 5 → 1 → 6 → 3 → 7。
递归实现
python
def inorder_recursive(root: TreeNode) -> list[int]:
"""中序遍历（递归），返回节点值序列"""
res = []
def dfs(node):
if node:
dfs(node.left) # 递归遍历左子树
res.append(node.val) # 访问根节点
dfs(node.right) # 递归遍历右子树
dfs(root)
return res
非递归实现
中序遍历的非递归需先遍历至最左叶子节点，再回溯访问根节点和右子树：
1.初始节点为根节点；
2.若当前节点非空或栈非空：
a. 当前节点非空时，入栈并移至左子节点（遍历左子树）；
b. 当前节点为空时，弹出栈顶节点，访问其值，再移至右子节点（访问根节点后遍历右子树）；
3.重复步骤2，直至当前节点为空且栈空。
python
def inorder_iterative(root: TreeNode) -> list[int]:
"""中序遍历（非递归），返回节点值序列"""
res = []
stack = []
node = root
while stack or node:
while node: # 遍历至最左叶子节点
stack.append(node)
node = node.left
node = stack.pop() # 弹出栈顶（左子树已遍历完）
res.append(node.val) # 访问根节点
node = node.right # 遍历右子树
return res
（3）后序遍历（Postorder Traversal）
规则：左子树 → 右子树 → 根节点（左右根）。
示例：对图6-3的二叉树，后序遍历序列为：8 → 4 → 5 → 2 → 6 → 7 → 3 → 1。
递归实现
python
def postorder_recursive(root: TreeNode) -> list[int]:
"""后序遍历（递归），返回节点值序列"""
res = []
def dfs(node):
if node:
dfs(node.left) # 递归遍历左子树
dfs(node.right) # 递归遍历右子树
res.append(node.val) # 访问根节点
dfs(root)
return res
非递归实现（双栈法）
后序遍历的非递归较复杂，双栈法是直观方案：
1.栈1入根节点；
2.栈1非空时，弹出节点并压入栈2，再将其左、右子节点依次入栈1（保证栈2弹出顺序为“根→右→左”）；
3.栈1空时，栈2弹出所有节点，顺序即为“左→右→根”。
python
def postorder_iterative(root: TreeNode) -> list[int]:
"""后序遍历（非递归，双栈法），返回节点值序列"""
res = []
if not root:
return res
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node.val) # 节点值暂存栈2
if node.left: # 左子节点先入栈1（后压入栈2）
stack1.append(node.left)
if node.right: # 右子节点后入栈1（先压入栈2）
stack1.append(node.right)
return stack2[::-1] # 栈2逆序即为后序序列
6.4.2 广度优先遍历（BFS）——层序遍历
规则：从根节点开始，按层次（第1层→第2层→…→第k层）依次访问各层节点，同一层节点按从左到右顺序访问。
示例：对图6-3的二叉树，层序遍历序列为：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8。
实现方式（队列）
层序遍历需用队列（FIFO）存储待访问节点：
1.根节点入队；
2.队列非空时，出队队首节点，访问其值；
3.若节点有左子节点，左子节点入队；
4.若节点有右子节点，右子节点入队；
5.重复步骤2~4，直至队空。
python
from collections import deque
def levelorder(root: TreeNode) -> list[int]:
"""层序遍历，返回节点值序列"""
res = []
if not root:
return res
q = deque([root]) # 用双端队列存储待访问节点
while q:
node = q.popleft()
res.append(node.val) # 访问当前节点
if node.left:
q.append(node.left) # 左子节点入队
if node.right:
q.append(node.right) # 右子节点入队
return res
扩展：若需按层分组（如返回[[1], [2,3], [4,5,6,7], [8]]），可在每层遍历前记录队列长度（当前层节点数）：
python
def levelorder_grouped(root: TreeNode) -> list[list[int]]:
"""层序遍历（按层分组），返回二维节点值序列"""
res = []
if not root:
return res
q = deque([root])
while q:
level_size = len(q) # 当前层节点数
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
6.5 遍历算法的应用
遍历是二叉树操作的基础，以下是典型应用场景：
6.5.1 二叉树的构建
已知前序+中序遍历序列（或中序+后序遍历序列），可唯一确定一棵二叉树（需保证节点值不重复）。
示例：已知前序序列[1,2,4,8,5,3,6,7]和中序序列[8,4,2,5,1,6,3,7]，构建二叉树步骤：
1.前序序列的第一个元素为根节点（1）；
2.在中序序列中，根节点左侧为左子树中序序列[8,4,2,5]，右侧为右子树中序序列[6,3,7]；
3.左子树节点数为4，故前序序列中根节点后4个元素为左子树前序序列[2,4,8,5]；
4.递归构建左子树（根2，中序[8,4,2,5]）和右子树（根3，中序[6,3,7]）。
6.5.2 二叉树的深度计算
利用后序遍历（先计算左右子树深度，取最大值加1即为当前节点深度）：
python
def tree_depth(root: TreeNode) -> int:
"""计算二叉树的深度（根到最远叶子的路径长度）"""
if not root:
return 0
left_depth = tree_depth(root.left)
right_depth = tree_depth(root.right)
return max(left_depth, right_depth) + 1
6.5.3 判断平衡二叉树
平衡二叉树是指任意节点的左右子树深度差不超过1，可结合后序遍历和深度计算实现：
python
def is_balanced(root: TreeNode) -> bool:
"""判断二叉树是否为平衡二叉树"""
def dfs(node):
if not node:
return 0 # 空树深度为0，且平衡
left_depth = dfs(node.left)
if left_depth == -1: # 左子树不平衡
return -1
right_depth = dfs(node.right)
if right_depth == -1 or abs(left_depth - right_depth) > 1: # 右子树不平衡或当前节点不平衡
return -1
return max(left_depth, right_depth) + 1 # 返回当前节点深度
return dfs(root) != -1
小结
本章系统介绍了树的基本概念（定义、术语）、二叉树的特性（定义、特殊形态、性质）、存储结构（顺序存储、链式存储）及核心遍历算法（前序、中序、后序、层序）。
二叉树的遍历是重点，需掌握递归与非递归实现：递归简洁但依赖系统栈，非递归需手动用栈（深度优先）或队列（广度优先）模拟。遍历算法是解决二叉树问题的基础，如构建、深度计算、平衡判断等均需基于遍历思想。
后续章节将学习二叉树的扩展结构（如二叉搜索树、堆、红黑树），其操作（插入、删除、查询）均以本章遍历和性质为基础。
本站原创，转载请注明出处：https://www.xin3721.com/ArticlePrograme/robot/49259.html
