数据结构｜二叉树（四）：链式结构与递归遍历——前中后序、层序遍历、结点统计与高度

写在前面

前面的二叉树专题中，我们从基础概念一路讲到完全二叉树、堆结构与 Top-K 算法。堆之所以能直接用数组存储，核心在于完全二叉树结构规整，通过下标即可快速定位父子结点。

但普通二叉树的形态并不固定，结点分布可能极不规则。如果强行用数组存储，会产生大量空置位置，造成空间浪费。因此从本篇开始，我们引入更通用的二叉树链式存储结构：每个结点保存自身数据，同时存储左、右孩子的指针。

本篇将完成四部分内容：定义链式二叉树结构并手动构造测试树；深入讲解前序、中序、后序三种递归遍历与层序遍历；实现结点总数、叶子结点数、树高度、第 K 层结点数等经典递归接口；最终提炼二叉树递归的核心分治思想。

为了把重心放在结构理解与递归思维上，本篇先手动创建固定二叉树用于测试。根据数据自动递归建树的方法，后续会单独详细讲解。

一、二叉树的链式存储结构

1.1 结点结构定义

普通二叉树的每个结点需要包含三部分信息：

• 结点存储的数据；
• 左孩子结点的指针；
• 右孩子结点的指针。

对应代码定义：

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
} BTNode;

• 这里通过typedef统一重命名数据类型与结点类型，方便后续修改。
• 本篇用字符A、B、C...演示树结构，因此BTDataType定义为char；后续若需存储整数，只需修改这一行即可，其余接口基本无需改动。
• left与right分别指向左右孩子结点，若对应孩子不存在，则赋值为NULL。

1.2 为什么普通二叉树更适合链式结构

以一棵偏斜树为例：

        A
       /
      B
     /
    D

使用链式结构时，每个有效结点仅存储「数据 + 左指针 + 右指针」，不存在的孩子直接用NULL表示，没有额外空间浪费。

普通二叉树形态灵活多变，链式结构是最自然的存储方式，也是后续二叉搜索树、AVL 树、红黑树等高级结构的基础。

二、手动创建一棵测试二叉树

为了统一后续所有测试，本篇固定使用以下满二叉树作为示例：

            A
          /   \
         B     C
        / \   / \
       D   E F   G

先封装一个创建结点的函数：

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

再手动连接各结点，构建整棵树：

BTNode* CreateBinaryTree()
{
	BTNode* A = BuyBTNode('A');
	BTNode* B = BuyBTNode('B');
	BTNode* C = BuyBTNode('C');
	BTNode* D = BuyBTNode('D');
	BTNode* E = BuyBTNode('E');
	BTNode* F = BuyBTNode('F');
	BTNode* G = BuyBTNode('G');

	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	C->left = F;
	C->right = G;

	return A;
}

手动建树仅用于学习测试。实际开发中会通过数据递归生成二叉树，包括利用空结点标记还原树形结构，后续会专门讲解。

三、理解递归遍历：叶子结点也有左右子树

二叉树与链表的核心区别在于：链表只有一条后继路径，而二叉树每个结点都有左、右两条分支。

遍历一个结点后，必须分别处理它的左子树和右子树。即便是叶子结点，从递归视角看，也可以理解为拥有两棵空子树：

      D
     / \
    N   N

其中N = NULL。也就是说，叶子结点的递归过程是：

访问结点 D
↓
递归访问 D 的左子树（NULL，直接返回）
↓
递归访问 D 的右子树（NULL，直接返回）

理解这一点，是真正掌握二叉树递归的关键。

四、前中后序遍历的核心区别

三种递归遍历的代码框架几乎完全一致，唯一区别就是访问根结点的时机不同。

下面基于测试树，分别完整走一遍遍历流程。

五、前序遍历：根 → 左 → 右

前序规则：先访问当前结点，再遍历左子树，最后遍历右子树。

从根结点 A 开始：

1. 访问 A，进入左子树 B；
2. 访问 B，进入左子树 D；
3. 访问 D，左子树 NULL 返回，右子树 NULL 返回；
4. 回到 B，进入右子树 E；
5. 访问 E，左右子树均为 NULL，返回；
6. 回到 A，进入右子树 C；
7. 同理依次访问 C、F、G。

包含空结点的完整前序序列：

A B D N N E N N C F N N G N N

忽略空结点后：

A B D E C F G

代码实现：

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

六、中序遍历：左 → 根 → 右

中序规则：先遍历左子树，再访问当前结点，最后遍历右子树。

从根结点 A 开始，一路向左走到 D：

1. D 的左子树 NULL，返回；
2. 访问 D；
3. D 的右子树 NULL，返回；
4. 回到 B，访问 B；
5. 遍历 B 的右子树 E，同理得到 N E N。

左半棵树中序序列：N D N B N E N

同理遍历右半棵树，最终完整序列：

N D N B N E N A N F N C N G N

忽略空结点后：

D B E A F C G

代码实现：

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

七、后序遍历：左 → 右 → 根

后序规则：先遍历左子树，再遍历右子树，最后访问当前结点。

以结点 D 为例：

1. 左子树 NULL，返回；
2. 右子树 NULL，返回；
3. 访问 D。

得到序列：N N D

同理推导整棵树，完整序列：

N N D N N E B N N F N N G C A

忽略空结点后：

D E B F G C A

代码实现：

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

三种遍历代码高度相似，仅仅是printf语句的位置不同。打印N是为了完整展示递归路径，实际使用时空结点直接return即可。

八、层序遍历：一层一层横向访问

前中后序都属于深度优先遍历：沿着一条路径走到头，再回溯处理其他分支。

层序遍历则完全不同，它是广度优先：按层次从上到下、每层从左到右依次访问结点。

对于测试树，层序结果为：

A B C D E F G

8.1 层序遍历的核心：队列

层序遍历需要借助队列实现，核心逻辑：

1. 根结点入队；
2. 队头结点出队，打印该结点；
3. 若左孩子存在，左孩子入队；
4. 若右孩子存在，右孩子入队；
5. 重复步骤 2-4，直到队列为空。

过程演示：

初始队列：[A]
A出队 → 输出A → B、C入队 → 队列：[B C]
B出队 → 输出B → D、E入队 → 队列：[C D E]
C出队 → 输出C → F、G入队 → 队列：[D E F G]
D、E、F、G依次出队 → 输出完整序列

8.2 代码实现

这里用数组模拟简易队列，也可以直接复用之前实现的链式队列，只需将存储类型改为BTNode*。

void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;

	int size = BinaryTreeSize(root);
	BTNode** queue = (BTNode**)malloc(sizeof(BTNode*) * size);
	if (queue == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	int front = 0, rear = 0;
	queue[rear++] = root;

	while (front < rear)
	{
		BTNode* cur = queue[front++];
		printf("%c ", cur->data);

		if (cur->left)
			queue[rear++] = cur->left;
		if (cur->right)
			queue[rear++] = cur->right;
	}

	free(queue);
}

九、二叉树结点总数

接口：int BinaryTreeSize(BTNode* root);

求整棵树的有效结点总数，这里介绍三种思路，重点推荐分治递归法。

方法一：全局变量计数

定义全局变量count，遍历过程中每遇到一个有效结点就加 1。 优点是直观易懂，缺点是多次调用前必须重置计数器，否则结果会累加。

static int g_size = 0;
void BinaryTreeSizeCount(BTNode* root)
{
	if (root == NULL)
		return;
	g_size++;
	BinaryTreeSizeCount(root->left);
	BinaryTreeSizeCount(root->right);
}

方法二：指针传参计数

由外部创建计数变量，传入地址进行修改，避免全局变量的问题。

void BinaryTreeSizeCount(BTNode* root, int* psize)
{
	assert(psize);
	if (root == NULL)
		return;
	(*psize)++;
	BinaryTreeSizeCount(root->left, psize);
	BinaryTreeSizeCount(root->right, psize);
}

方法三：分治递归（推荐）

核心思想：当前树的结点数 = 左子树结点数 + 右子树结点数 + 1（当前结点）。

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right)
		+ 1;
}

这种写法最能体现二叉树递归的分治思想：把大树问题拆解为两棵小树的同类问题，逐层递归到空树再向上返回结果。

十、二叉树叶子结点个数

接口：int BinaryTreeLeafSize(BTNode* root);

叶子结点的判定条件：left == NULL && right == NULL。

递归分三种情况：

1. 空树：返回 0；
2. 当前结点是叶子：返回 1；
3. 非叶子结点：叶子数 = 左子树叶子数 + 右子树叶子数。

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}

测试树共有 D、E、F、G 四个叶子结点，结果为 4。

十一、二叉树高度

接口：int BinaryTreeHeight(BTNode* root);

约定：空树高度为 0，只有根结点高度为 1。

递归公式：当前树高度 = max(左子树高度, 右子树高度) + 1。

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);

	return leftHeight > rightHeight
		? leftHeight + 1
		: rightHeight + 1;
}

重要提醒：不要重复调用递归

如果写出以下代码：

// 不推荐！重复递归，效率低下
return BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right)
	? BinaryTreeHeight(root->left) + 1
	: BinaryTreeHeight(root->right) + 1;

比较时已经计算过一次左右子树高度，三目运算符取值时又会重复计算一次，树越大性能损耗越严重。

正确做法是先用变量保存计算结果，再进行比较，当然也可以用fmax函数。

十二、二叉树第 K 层结点个数

接口：int BinaryTreeLevelKSize(BTNode* root, int k);

这道题的经典递归思路非常巧妙：把当前树第 K 层的问题，转化为左右子树第 K-1 层的问题。

递归逻辑：

1. k == 1：当前结点就是目标层，返回 1；
2. k > 1：第 K 层结点数 = 左子树第 K-1 层结点数 + 右子树第 K-1 层结点数；
3. 空树返回 0。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

对于测试树：第 1 层 1 个，第 2 层 2 个，第 3 层 4 个，第 4 层 0 个。

这道题很好地体现了递归的精髓：不需要一次算出整棵树的答案，只需要把问题拆解成规模更小、结构相同的子问题。

十三、本篇文章代码

本篇完整代码已上传 Gitee 仓库，新增BinaryTree.h、BinaryTree.c、BinaryTree_Test.c三个独立文件。

• 头文件定义链式二叉树结点与全部接口；
• 源文件完成前中后序递归遍历、层序遍历，以及结点统计、叶子计数、树高度、第 K 层结点个数等经典递归实现；
• 测试文件内置满二叉树样例，可直接编译运行，复现文中全部输出。

13.1 仓库地址：

数据结构/BinaryTree · Luminous/Code_2026 - 码云 - 开源中国

13.2.1头文件 BinaryTree.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
} BTNode;

// 创建结点
BTNode* BuyBTNode(BTDataType x);
// 手动创建测试二叉树
BTNode* CreateBinaryTree();

// 前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 中序遍历
void BinaryTreeInOrder(BTNode* root);
// 后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);

// 二叉树结点个数（分治）
int BinaryTreeSize(BTNode* root);
// 指针传参统计结点个数
void BinaryTreeSizeCount(BTNode* root, int* psize);
// 叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树高度
int BinaryTreeHeight(BTNode* root);
// 第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

13.2.2 实现代码 BinaryTree.c

#include "BinaryTree.h"

// 创建一个二叉树结点
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

// 手动创建测试二叉树
BTNode* CreateBinaryTree()
{
	BTNode* A = BuyBTNode('A');
	BTNode* B = BuyBTNode('B');
	BTNode* C = BuyBTNode('C');
	BTNode* D = BuyBTNode('D');
	BTNode* E = BuyBTNode('E');
	BTNode* F = BuyBTNode('F');
	BTNode* G = BuyBTNode('G');

	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	C->left = F;
	C->right = G;

	return A;
}

// 前序遍历：根 左 右
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

// 中序遍历：左 根 右
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

// 后序遍历：左 右 根
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

// 二叉树结点总数（分治递归）
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right)
		+ 1;
}

// 指针传参统计结点个数
void BinaryTreeSizeCount(BTNode* root, int* psize)
{
	assert(psize);
	if (root == NULL)
		return;

	(*psize)++;
	BinaryTreeSizeCount(root->left, psize);
	BinaryTreeSizeCount(root->right, psize);
}

// 叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}

// 二叉树高度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);

	return leftHeight > rightHeight
		? leftHeight + 1
		: rightHeight + 1;
}

// 第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

// 层序遍历（数组模拟队列）
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;

	int size = BinaryTreeSize(root);
	BTNode** queue = (BTNode**)malloc(sizeof(BTNode*) * size);
	if (queue == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	int front = 0, rear = 0;
	queue[rear++] = root;

	while (front < rear)
	{
		BTNode* cur = queue[front++];
		printf("%c ", cur->data);

		if (cur->left)
			queue[rear++] = cur->left;
		if (cur->right)
			queue[rear++] = cur->right;
	}

	free(queue);
}

13.2.3测试代码 test.c

#include "BinaryTree.h"

int main(void)
{
	BTNode* root = CreateBinaryTree();

	printf("前序遍历：\n");
	BinaryTreePrevOrder(root);
	printf("\n\n");

	printf("中序遍历：\n");
	BinaryTreeInOrder(root);
	printf("\n\n");

	printf("后序遍历：\n");
	BinaryTreePostOrder(root);
	printf("\n\n");

	printf("层序遍历：\n");
	BinaryTreeLevelOrder(root);
	printf("\n\n");

	printf("二叉树结点个数：%d\n", BinaryTreeSize(root));

	int size = 0;
	BinaryTreeSizeCount(root, &size);
	printf("指针统计结点个数：%d\n", size);

	printf("叶子结点个数：%d\n", BinaryTreeLeafSize(root));
	printf("二叉树高度：%d\n", BinaryTreeHeight(root));

	for (int k = 1; k <= 4; k++)
	{
		printf("第%d层结点个数：%d\n", k, BinaryTreeLevelKSize(root, k));
	}

	return 0;
}

13.3 实际输出

写在最后

从链式二叉树开始，递归思想贯穿了所有核心操作。

链表只有一条next路径，而二叉树每个结点都有left和right两棵子树，天然适合分治：把一个大树的问题，拆成左右两个小树的同类问题，递归求解再合并结果。

前中后序遍历看似三种不同方法，实则只是根结点访问时机的差异；结点总数、叶子数、高度、第 K 层结点数，本质上都是同一套递归框架的变体。

本篇通过手动建树把链式结构和递归接口练熟，接下来我们会继续研究二叉树的递归创建与进阶操作，之前遍历时特意保留的空结点标记N，也会在后续发挥关键作用。