以下是基本知识点，大家可以快速过一下。

在数据结构的知识体系中，树是一种重要的非线性数据结构，它以分层的方式组织数据，广泛应用于数据库索引、文件系统、编译器语法分析等领域。掌握树的基本知识点，是理解更复杂数据结构（如堆、红黑树、B + 树）的基础，以下从核心概念、重要特性、常见类型及遍历方式四个维度进行系统总结。​

一、树的定义与基本概念​

树是由n（n≥0）个节点组成的有限集合，当n=0时称为 “空树”；当n>0时，树满足两个条件：一是存在且仅存在一个称为 “根” 的节点，它没有前驱节点；二是其余n-1个节点可分为m（m≥0）个互不相交的有限子集，每个子集本身又是一棵独立的树，称为根节点的 “子树”。​

在树的结构中，还有多个高频基础概念需要明确：​

• 节点的度：一个节点拥有的子树数量（即直接子节点的个数）。例如，根节点若有 3 个直接子节点，其度为 3。​

• 树的度：树中所有节点的度的最大值。若一棵树中所有节点的度不超过 2，这棵树的度就是 2。​

• 叶子节点（终端节点）：度为 0 的节点，即没有子节点的节点，通常位于树的最底层。​

• 非叶子节点（非终端节点）：度大于 0 的节点，除叶子节点外的所有节点都属于此类，包括根节点。​

• 父节点与子节点：若一个节点含有子树，该节点称为子树的 “父节点”，子树的根节点称为该节点的 “子节点”；同一父节点的子节点之间互称 “兄弟节点”。​

• 祖先与后代：从根节点到某一节点的路径上，所有经过的节点（包括根节点）都是该节点的 “祖先”；反之，某一节点的所有子树中的节点（包括子节点、孙节点等）都是该节点的 “后代”。​

• 节点的层次：通常规定根节点位于第 1 层（部分教材定义为第 0 层，需注意统一标准），根节点的子节点位于第 2 层，以此类推，节点的层次反映了它在树中的 “深度”。​

• 树的高度（深度）：树中节点的最大层次，空树的高度为 0，仅含根节点的树的高度为 1。​

二、树的重要特性​

树的结构决定了其具有独特的数学特性，这些特性是解决树相关问题的关键依据，核心特性包括：​

1. 节点与边的关系：若一棵树上有n个节点，则它必有n-1条边。因为树是 “无环的连通图”，根节点没有父节点（无入边），其余每个节点都恰好有 1 条来自父节点的入边，因此边数 = 节点数 - 1。​

1. 层次与节点数的极限：对于深度为k（k≥1）的树，其节点总数的范围是[k, 2^k - 1]。其中，最少节点数对应 “每一层仅 1 个节点” 的情况（即树退化为一条链）；最多节点数对应 “每一层节点数都达到最大值” 的情况，即第i层有2^(i-1)个节点（此类树称为 “满二叉树”，是特殊的完全二叉树）。​

1. 度与叶子节点的关系：设树的总节点数为n，度为 0 的节点数（叶子节点）为n0，度为 1 的节点数为n1，度为 2 的节点数为n2，…，度为m的节点数为nm，则有两个核心等式：​

• 总节点数等式：n = n0 + n1 + n2 + ... + nm（所有度的节点数之和）；​

• 总边数等式：n - 1 = 0×n0 + 1×n1 + 2×n2 + ... + m×nm（边数 = 各节点的度之和，因为每个节点的度对应其出边数）。​

联立两式可推出：n0 = 1 + n2 + 2n3 + ... + (m-1)nm。对于二叉树（m=2），该式简化为n0 = n1 + 2n2 + 1，进一步可推导：若二叉树中没有度为 1 的节点（n1=0），则叶子节点数 = 度为 2 的节点数 + 1（即n0 = n2 + 1），这是二叉树问题中最常用的推论之一。​

三、常见的树结构类型​

根据节点度的限制、节点值的有序性等特征，树可分为多种类型，其中二叉树、完全二叉树、满二叉树、二叉搜索树是最基础且应用最广的类型：​

1. 二叉树​

二叉树是 “每个节点的度不超过 2” 的树，即每个节点最多有左、右两个子节点（分别称为 “左子树” 和 “右子树”，且左右子树有明确的顺序，不能随意交换）。二叉树是树结构的 “核心分支”，因为任何普通树都可以通过 “左孩子右兄弟” 的方式转换为二叉树，方便计算机存储和处理。​

2. 满二叉树​

满二叉树是二叉树的特殊形式，满足 “每一层的节点数都达到最大值”：第i层有2^(i-1)个节点，且所有叶子节点都位于同一层。例如，深度为 3 的满二叉树，总节点数为2^3 - 1 = 7，第 1 层 1 个节点、第 2 层 2 个节点、第 3 层 4 个节点，且所有叶子节点都在第 3 层。​

3. 完全二叉树​

完全二叉树是 “按层序遍历顺序，除最后一层外，其余各层节点数均满，且最后一层的节点从左到右连续排列（不能有空缺）” 的二叉树。完全二叉树的核心特点是 “结构紧凑”，没有 “稀疏” 的节点，因此可以用数组高效存储（根节点存在下标 1，左子节点下标 = 父节点下标 ×2，右子节点下标 = 父节点下标 ×2+1）。满二叉树是完全二叉树的特殊情况，但完全二叉树不一定是满二叉树（例如深度为 3 的完全二叉树，最后一层可能有 1-4 个节点）。​

4. 二叉搜索树（BST，Binary Search Tree）​

二叉搜索树是 “具有有序性” 的二叉树，其左、右子树满足：对于树中的任意一个节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值（若存在相等值，需根据具体规则定义，通常不允许重复值或规定重复值在右子树）。二叉搜索树的核心优势是 “查找效率高”—— 若树是平衡的，查找、插入、删除操作的时间复杂度均为O(log n)，但在极端情况下（树退化为链），时间复杂度会降为O(n)，因此后续衍生出平衡二叉树（如 AVL 树、红黑树）来解决这一问题。​

四、树的遍历方式​

树的遍历是 “按一定顺序访问树中所有节点，且每个节点仅访问一次” 的操作，是树相关算法的基础。根据访问根节点的时机不同，二叉树的遍历可分为四种核心方式（普通树的遍历可先转换为二叉树再执行）：​

1. 前序遍历（Pre-order Traversal）​

• 遍历顺序：根节点 → 左子树 → 右子树（“根左右”）。​

• 特点：先访问根节点，再递归遍历左、右子树，适合需要 “先处理根节点信息” 的场景（如复制树、获取树的前缀表达式）。​

• 示例：对于根为 A、左子树为 B（B 的左子树为 D、右子树为 E）、右子树为 C（C 的右子树为 F）的二叉树，前序遍历结果为：A → B → D → E → C → F。​

2. 中序遍历（In-order Traversal）​

• 遍历顺序：左子树 → 根节点 → 右子树（“左根右”）。​

• 特点：中序遍历是二叉搜索树的 “关键遍历方式”—— 若对二叉搜索树执行中序遍历，得到的结果是 “从小到大的有序序列”，可用于验证二叉搜索树的有效性、获取有序数据等。​

• 示例：上述示例二叉树的中序遍历结果为：D → B → E → A → C → F。​

3. 后序遍历（Post-order Traversal）​

• 遍历顺序：左子树 → 右子树 → 根节点（“左右根”）。​

• 特点：后序遍历会 “最后访问根节点”，适合需要 “先处理子节点，再处理父节点” 的场景（如删除树、计算树的后缀表达式、统计子树节点数）。​

• 示例：上述示例二叉树的后序遍历结果为：D → E → B → F → C → A。​

4. 层序遍历（Level-order Traversal）​

• 遍历顺序：按节点的层次从左到右依次访问，即先访问第 1 层（根节点），再访问第 2 层的所有节点，以此类推（“从上到下，从左到右”）。​

• 特点：层序遍历需借助 “队列” 实现（先进先出），适合需要 “按层次处理节点” 的场景（如计算树的高度、判断完全二叉树、广度优先搜索 BFS）。​

• 示例：上述示例二叉树的层序遍历结果为：A → B → C → D → E → F。

下面演示一下树的几种遍历方式的代码，这里采用数组的方式，更加简便，结构体和指针的方式想必大家都耳熟能详了，这里就不在赘述

​
#include<iostream>
#include<queue>
using namespace std;
const int N = 1e5 + 9;
/*ls[i] 存储节点 i 的左子节点编号
rs[i] 存储节点 i 的右子节点编号
节点编号从 1 开始，0 表示空节点*/
int ls[N], rs[N];
//先序遍历
void dfs1(int x)
{
	cout << x << ' ';
	if (ls[x])dfs1(ls[x]);
	if (rs[x])dfs1(rs[x]);
}
// 中序
void dfs2(int x)
{
	if (ls[x])dfs2(ls[x]);
	cout << x << ' ';
	if (rs[x])dfs2(rs[x]);
}
// 后序
void dfs3(int x)
{
	if (ls[x])dfs3(ls[x]);
	if (rs[x])dfs3(rs[x]);
	cout << x << ' ';
}
//层序遍历（bfs），采用队列
void bfs() 
{
	queue<int> q;        // 创建一个队列，用于存储待处理的节点
	q.push(1);           // 从根节点1开始处理，将根节点加入队列
	while (q.size()) 
	{   // 只要队列不为空，就继续处理
		int x = q.front(); q.pop();  // 取出队列的第一个节点
		cout << x << ' ';            // 输出当前节点
		// 将当前节点的左右子节点加入队列（如果存在）
		if (ls[x]) q.push(ls[x]);    // 左子节点入队
		if (rs[x]) q.push(rs[x]);    // 右子节点入队
	}
}
/*初始状态：队列中只有根节点 [1]
第一次循环：
取出节点 1，输出 1
将节点 1 的左子节点 2 和右子节点 3 入队
队列变为 [2, 3]
第二次循环：
取出节点 2，输出 2
将节点 2 的左子节点 4 和右子节点 5 入队
队列变为 [3, 4, 5]
第三次循环：
取出节点 3，输出 3
节点 3 没有子节点，队列变为 [4, 5]
第四次循环：
取出节点 4，输出 4
节点 4 没有子节点，队列变为 [5]
第五次循环：
取出节点 5，输出 5
节点 5 没有子节点，队列为空，循环结束
最终输出结果为：1 2 3 4 5，这正是按层次遍历的顺序。*/
int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> ls[i] >> rs[i];
	dfs1(1);
	cout << '\n';
	dfs2(1);
	cout << '\n';
	dfs3(1);
	cout << '\n';
	bfs();
	return 0;
}

​