数据结构（C语言篇）：（十四）链式结构二叉树

前言

链式结构二叉树是计算机科学中一种基础且重要的数据结构，广泛应用于搜索、排序、数据库索引和算法优化等领域。它以节点和指针的动态链接方式组织数据，兼具逻辑清晰与操作灵活的特点，能够高效实现数据的层次化存储与检索。本文将深入探讨链式二叉树的实现原理，从节点设计、内存分配到核心操作（如插入、删除、遍历）的代码实现，结合时间复杂度和空间复杂度分析，为开发者提供兼具理论深度与实践价值的参考方案。就让我们正式开始吧！

一、实现链式结构二叉树

链式二叉树是一种常见的二叉树数据结构，其每个节点最多包含两个子节点（左子节点和右子节点），节点之间通过指针或引用来进行连接。它具有如下特点：

• 每个节点包含数据域和两个指针域（左指针、右指针）；
• 左指针指向左子树，右指针指向右子树；
• 没有子节点的指针为空（null）；
• 适合动态存储，不需要预先分配固定大小的空间。

我们根据上述的条件可以将链式二叉树的结构定义如下：

typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{
    struct BinTreeNode* left; // 指向当前结点左孩⼦
    struct BinTreeNode* right; // 指向当前结点右孩⼦
    BTDataType val; // 当前结点值域
}BTNode;

接下来我们先来实现一下二叉树的结点创建函数：buyNode( )函数。

（1）实现逻辑：

1. 通过 malloc 动态分配一块大小为 sizeof(BTNode) 的内存空间，用于存储新节点；

2. 将传入的字符 x 赋值给新节点的数据域（data）；

3. 将新节点的左指针（left）和右指针（right）初始化为 NULL（表示暂时没有子节点）；

4. 返回新创建结点的指针。

完整代码如下：

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

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

	return newnode;
}

（2）底层原理

1. 内存分配：使用 malloc 从堆（heap）中分配内存，这部分内存需要手动释放（通常在销毁树时通过递归完成）。

2. 结构体布局：假设 BTNode 定义为包含 char data 和两个 BTNode* 指针的结构体，内存布局为连续的一块空间，依次存储数据和指针。

3. 指针初始化：将左右指针设为 NULL 是良好的编程习惯，避免野指针（指向不确定内存的指针）导致的内存访问错误。

（3）应用示例

// 假设BTNode定义如下
typedef struct BTNode {
    char data;
    struct BTNode* left;
    struct BTNode* right;
} BTNode;

// 构建一个简单二叉树
BTNode* buildSimpleTree() {
    // 使用buyNode创建节点
    BTNode* root = buyNode('A');
    root->left = buyNode('B');
    root->right = buyNode('C');
    root->left->left = buyNode('D');
    
    return root;
}

上面的代码将创建如下结构的二叉树：

    A
   / \
  B   C
 /
D

（4）执行流程

我们以 buyNode('X') 调用为例，执行步骤如下所示：

1. 调用malloc(sizeof(BTNode)) 分配内存，返回指向该内存块的指针，赋值给 newnode。

2. 将字符 'X' 存储到 newnode->data 中。

3. 将 newnode->left 和 newnode->right 都设置为 NULL。

4. 返回newnode 指针，调用者可使用该指针将新节点链接到二叉树中。

实现了链式二叉树创建结点的函数，我们来简单回顾一下二叉树的概念。二叉树分为空树和非空二叉树，非空二叉树是由根结点、根结点的左子树、根结点的右子树组成的。根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的，因此二叉树的定义是递归式的，后序链式二叉树的操作中基本都是按照该概念实现的。

1.1 前中后序遍历

谈到二叉树的操作，那就肯定离不开二叉树的遍历。我们先来看看二叉树的遍历有哪些方式。

1.1.1 遍历规则

按照规则，二叉树的遍历分为：前序、中序、后序的递归结构遍历：

（1）前序遍历（Preorder Traversal，亦称先序遍历）：访问根节点的操作发生在遍历其左右子树之前。访问顺序为：根节点、左子树、右子树。

（2）中序遍历（Inorder Traversal）：访问根节点的操作发生在遍历其左右子树之中（间）。访问顺序为：左子树、根节点、右子树。

（3）后序遍历（Postorder Traversal）：访问根节点的造作发生在遍历其左右子树之后。访问顺序为：左子树、右子树、根节点。

1.1.2 代码实现

下面我们就来分别实现一下这三种遍历方式：

//前序遍历---根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
//后序遍历--左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

可以看到上述三种遍历方式的逻辑层次上，都使用了递归结构。这种实现方式能够有效帮助我们提高遍历的效率。

我们也可以将上述代码的执行流程以图解的形式，更加直观的理解，以前序遍历为例：

函数递归栈帧图如下：

我们最后可以分别得到三种遍历方式的运行结果：

前序遍历结果：1 2 3 4 5 6 中序遍历结果：3 2 1 5 4 6 后序遍历结果：3 1 5 6 4 1

1.2 结点个数以及高度等的实现

1.2.1 BinaryTreeSize()函数（节点总数）

（1）实现逻辑

1. 基准条件：若当前的结点为NULL（空树或空子树），返回 0（没有节点）。

2. 递归逻辑：非空结点时，当前节点计数为 1，加上左子树的节点总数和右子树的节点总数。

3. 公式表达：节点总数 = 1（当前节点） + 左子树节点数 + 右子树节点数。

完整代码如下：

//节点总数 = 1 + 左子树节点个数 + 右子树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

（2）底层原理

本质上是利用函数调用栈实现分治思想，将 "计算整棵树的节点数" 分解为 "计算左子树节点数" 和 "计算右子树节点数" 两个子问题。

该函数的遍历方式本质是后序遍历的应用，即先处理左子树，再处理右子树，最后计算当前节点。

（3）应用示例

假设存在如下二叉树（节点值为字符）：

    A
   / \
  B   C
 /   /
D   E

调用 BinaryTreeSize(root) 计算节点总数：

• 根节点 A 非空，触发递归：1 + 左子树（B）节点数 + 右子树（C）节点数；
• 左子树 B：1 + 左子树（D）节点数 + 右子树（NULL）节点数 → 1 + 1 + 0 = 2；
• 右子树 C：1 + 左子树（E）节点数 + 右子树（NULL）节点数 → 1 + 1 + 0 = 2；
• 最终结果：1 + 2 + 2 = 5（总节点数为 5）。

（4）执行流程

1. 调用 BinaryTreeSize(A)，A 非空，进入递归

2. 先计算左子树：调用 BinaryTreeSize(B)

B 非空，调用 BinaryTreeSize(D)：

D 非空，调用 BinaryTreeSize(D->left)（NULL）→ 返回 0；

调用 BinaryTreeSize(D->right)（NULL）→ 返回 0；

D 节点结果：1 + 0 + 0 = 1。

调用 BinaryTreeSize(B->right)（NULL）→ 返回 0。

B 节点结果：1 + 1 + 0 = 2。

3. 再计算右子树：调用 BinaryTreeSize(C)

C 非空，调用 BinaryTreeSize(E)；

E 非空，调用 BinaryTreeSize(E->left)（NULL）→ 返回 0；

调用 BinaryTreeSize(E->right)（NULL）→ 返回 0；

E 节点结果：1 + 0 + 0 = 1。

调用 BinaryTreeSize(C->right)（NULL）→ 返回 0。

C 节点结果：1 + 1 + 0 = 2。

4. 根节点 A 结果：1 + 2 + 2 = 5，返回最终结果。

1.2.2 BinaryTreeLeafSize( )函数（叶子结点个数）

（1）实现逻辑

• 基准条件：若当前节点为 NULL（空树或空子树），返回 0（无叶子节点）。
• 叶子节点判定：若当前节点的左子树和右子树均为 NULL（即没有子节点），则该节点是叶子节点，返回 1。
• 递归逻辑：非叶子节点时，叶子节点总数等于左子树的叶子节点数加上右子树的叶子节点数。

画图分析如下：

完整代码如下所示：

// ⼆叉树叶⼦结点个数
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);
}

（2）底层原理

1. 递归分解：将 "整棵树的叶子节点数" 分解为 "左子树叶子数" 和 "右子树叶子数" 的和。

2. 判定逻辑：通过 root->left == NULL && root->right == NULL 精准识别叶子节点。

（3）应用示例

假设有如下结构的二叉树：

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

其中叶子节点为 D、G、F，共三个。

调用 BinaryTreeLeafSize(root) 的计算过程如下所示：

• 根节点 A ：非叶子，结果 = 左子树（B）叶子数 + 右子树（C）叶子数
• 左子树 B：非叶子，结果 = 左子树（D）叶子数 + 右子树（NULL）叶子数 → 1 + 0 = 1
• 右子树 C：非叶子，结果 = 左子树（E）叶子数 + 右子树（F）叶子数

E 非叶子：结果 = 左子树（G）叶子数 + 右子树（NULL）叶子数 → 1 + 0 = 1

F 是叶子：结果 = 1

因此 C 的结果 = 1 + 1 = 2

• 最终总叶子数：1 + 2 = 3

（4）执行流程

以计算上述示例树的叶子数为例，步骤如下：

1. 调用 BinaryTreeLeafSize(A)，A 非叶子，进入递归

2. 计算左子树：BinaryTreeLeafSize(B)

B 非叶子，调用 BinaryTreeLeafSize(D)；

D 的左右子树均为 NULL → 是叶子，返回 1。

调用 BinaryTreeLeafSize(B->right)（NULL）→ 返回 0。

B 的结果：1 + 0 = 1。

3. 计算右子树：BinaryTreeLeafSize(C)

C 非叶子，调用 BinaryTreeLeafSize(E)

E 非叶子，调用 BinaryTreeLeafSize(G)

G 的左右子树均为 NULL → 是叶子，返回 1

调用 BinaryTreeLeafSize(E->right)（NULL）→ 返回 0

E 的结果：1 + 0 = 1

调用 BinaryTreeLeafSize(F)

F 的左右子树均为 NULL → 是叶子，返回 1

C 的结果：1 + 1 = 2

4. 总结果：1（B 的左子树） + 2（C 的子树） = 3

（5）注意事项

• 与节点总数的区别：该函数仅统计叶子节点（度为 0），而 BinaryTreeSize 统计所有节点。
• 递归边界：能正确处理空树（返回 0）和单节点树（根节点即为叶子，返回 1）的边界情况。
• 效率优化：无需额外辅助空间，递归过程直接通过返回值传递中间结果。

1.2.3 BinaryTreeLevelKSize( )函数（第K层结点个数）

（1）实现逻辑

该函数的核心逻辑在于递归的层次缩减。

首先我们依旧画个图来分析一下：

1. 基准条件：若当前节点为 NULL（空树或空子树），返回 0（该路径上无第 k 层节点）。

2. 层次判定：若 k == 1，表示当前节点所在层即为目标层，返回 1（当前节点计数）。

3. 递归逻辑：非目标层时，将问题转化为求左子树的第 k-1 层节点数与右子树的第 k-1 层节点数之和（每深入一层，目标层数减 1）。

完整代码如下所示：

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为第K层
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) 
		+ BinaryTreeLevelKSize(root->right,k-1);
}

（2）底层原理

• 层次映射：通过 k-1 的递归传递，将 "求第 k 层节点数" 转化为 "从子节点求第 k-1 层节点数"，本质上其实是将树的层次关系映射到递归深度上。
• 遍历特性：递归过程会覆盖所有可能路径，确保了第 k 层的每个节点都被计数。

（3）应用示例

我们假设有如下的二叉树（层次编号从 1 开始）：

        1（第1层）
       / \
      2   3（第2层）
     / \   \
    4   5   6（第3层）
   /
  7（第4层）

计算各层的结点个数：

• 第 1 层：BinaryTreeLevelKSize(root, 1) → 返回 1（仅节点 1）。
• 第 2 层：BinaryTreeLevelKSize(root, 2) → 左子树（2）的第 1 层 + 右子树（3）的第 1 层 → 1 + 1 = 2。
• 第 3 层：左子树（2）的第 2 层（1+1） + 右子树（3）的第 2 层（1） → 2 + 1 = 3。
• 第 4 层：仅左子树（4）的第 2 层有 1 个节点（7）→ 返回 1。

（4）执行流程

我们以计算第 3 层节点数为例，步骤如下：

1. 调用 BinaryTreeLevelKSize(root, 3)，root 为节点 1（非空，k≠1）。

2. 递归计算左子树（节点 2）的第 2 层：BinaryTreeLevelKSize(2, 2)。

• 节点 2 非空，k≠1，继续递归；
• 左子树（节点 4）的第 1 层：BinaryTreeLevelKSize(4, 1) → 返回 1；
• 右子树（节点 5）的第 1 层：BinaryTreeLevelKSize(5, 1) → 返回 1；
• 节点 2 的结果：1 + 1 = 2。

3. 递归计算右子树（节点 3）的第 2 层：BinaryTreeLevelKSize(3, 2)。

• 节点 3 非空，k≠1，继续递归；
• 左子树（NULL）的第 1 层 → 返回 0；
• 右子树（节点 6）的第 1 层：BinaryTreeLevelKSize(6, 1) → 返回 1；
• 节点 3 的结果：0 + 1 = 1。

4. 总结果：2（左子树） + 1（右子树） = 3（第 3 层共 3 个节点）。

1.2.4 BinaryTreeDepth( )函数（二叉树的深度/高度）

（1）实现逻辑

该函数的核心逻辑基于递归比较：

• 基准条件：若当前节点为 NULL（空树或空子树），返回 0（深度为 0）。
• 递归逻辑：非空节点时，先计算左子树的深度和右子树的深度。
• 结果计算：当前节点的深度 = 1（当前节点本身） + 左、右子树深度的最大值（取更深的子树作为路径延伸）。

画图分析如下：

完整代码如下：

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//根节点+max(左子树高度，右子树高度)
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

（2）底层原理

• 递归分解：将 "整棵树的深度" 分解为 "左子树深度" 和 "右子树深度" 的比较。
• 深度定义：树的深度为根节点到最远叶子节点的边数加 1（或节点数），这里采用 "节点数计数法"（根节点为第 1 层）。

（3）应用示例

假设有如下二叉树：

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

其深度计算过程如下所示：

• 根节点 A 的左子树（B）深度：B 的左子树（D）深度为 1，右子树（NULL）深度为 0 → B 的深度 = 1 + max (1, 0) = 2 → A 的左子树深度为 2。
• 根节点 A 的右子树（C）深度：C 的左子树（E）深度为 2（E→G），右子树（F）深度为 1 → C 的深度 = 1 + max (2, 1) = 3 → A 的右子树深度为 3。
• 整棵树的深度：1 + max (2, 3) = 4（最深路径为 A→C→E→G，共 4 个节点）。

（4）执行流程

以计算上述示例树的深度为例，步骤如下：

1. 调用BinaryTreeDepth(A)，A 非空。

2. 计算左子树深度：BinaryTreeDepth(B)。

• B 非空，计算 BinaryTreeDepth(D)：
  • D 非空，计算 BinaryTreeDepth(D->left)（NULL）→ 返回 0；
  • 计算 BinaryTreeDepth(D->right)（NULL）→ 返回 0；
  • D 的深度：1 + max (0, 0) = 1。
• 计算 BinaryTreeDepth(B->right)（NULL）→ 返回 0。
• B 的深度：1 + max (1, 0) = 2。

3. 计算右子树深度：BinaryTreeDepth(C)

• C 非空，计算 BinaryTreeDepth(E)。
  • E 非空，计算 BinaryTreeDepth(G)。
    • G 非空，计算其左右子树深度均为 0 → G 的深度 = 1 + 0 = 1。
  • 计算 BinaryTreeDepth(E->right)（NULL）→ 返回 0。
  • E 的深度：1 + max (1, 0) = 2。
• 计算 BinaryTreeDepth(F)。
  • F 非空，其左右子树深度均为 0 → F 的深度 = 1 + 0 = 1。
• C 的深度：1 + max (2, 1) = 3。

4. 整棵树的深度：1 + max (2, 3) = 4。

1.2.5 BinaryTreeFind()函数（查找值为x的结点）

（1）实现逻辑

首先我们来画图分析一下：

1. 基准条件：若当前节点为 NULL（空树或搜索到叶子节点的子树），返回 NULL（未找到）。

2. 匹配判定：若当前节点的数据域等于 x，直接返回当前节点的指针（找到目标）。

3. 递归查找：若当前节点不匹配，则先递归查找左子树；若左子树找到则返回结果，否则递归查找右子树。

4. 最终结果：若左右子树均未找到，返回 NULL。

完整代码如下所示：

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

（2）底层原理

• 遍历策略：本质是二叉树的先序遍历（根→左→右），优先检查当前节点，再依次搜索左、右子树。
• 查找范围：会遍历整棵树直到找到目标节点或搜索完所有节点，属于全树搜索。

（3）应用示例

假设有如下二叉树（节点值为整数）：

        1
       / \
      2   3
     / \   \
    4   5   6
       /
      7

• 查找 x=5：
  1. 根节点 1 不匹配，递归查找左子树（2）；
  2. 节点 2 不匹配，递归查找左子树（4）→ 不匹配；
  3. 回溯查找节点 2 的右子树（5）→ 匹配，返回节点 5 的指针。
• 查找 x=8：

遍历所有节点均不匹配，最终返回 NULL。

（4）执行流程

以查找 x=7 为例，步骤如下：

1. 调用 BinaryTreeFind(root, 7)，root 为节点 1（不匹配）；
2. 递归查找左子树：BinaryTreeFind(2, 7)（节点 2 不匹配）；
3. 递归查找节点 2 的左子树：BinaryTreeFind(4, 7)（节点 4 不匹配，其左右子树均为 NULL → 返回 NULL）；
4. 回溯查找节点 2 的右子树：BinaryTreeFind(5, 7)（节点 5 不匹配）；
5. 递归查找节点 5 的左子树：BinaryTreeFind(7, 7)（节点 7 匹配 → 返回节点 7 的指针）；
6. 上层函数接收到非 NULL 结果，依次回溯返回，最终返回节点 7 的指针。

该函数有如下的注意事项，需要大家多多留意：

• 查找顺序：先左后右的查找顺序决定了若树中存在多个值为 x 的节点，将返回第一个被遍历到的节点（左子树中的节点优先于右子树）。
• 与二叉搜索树的区别：该函数适用于普通二叉树的全树查找，而二叉搜索树可通过 "左小右大" 特性优化查找（时间复杂度

O (log n)

）。

• 空树处理：正确返回 NULL，符合 "空树中无任何节点" 的逻辑。
• 返回值意义：返回节点指针可直接操作找到的节点（如修改数据、调整子树等）。

1.2.6 BinaryTreeDestory()函数（销毁二叉树）

（1）实现逻辑

该函数的核心逻辑是基于后序递归释放的：

首先画图分析一下：

1. 基准条件：若当前节点指针（*root）为 NULL，直接返回（空树或已释放的子树）。

2. 递归释放：先递归销毁左子树，再递归销毁右子树（确保子节点内存先于父节点释放）。

3. 释放当前节点：调用 free(*root) 释放当前节点的内存。

4. 置空指针：将 *root 设为 NULL，避免野指针（指向已释放内存的指针）。

注：在这里函数参数使用了二级指针（BTNode**），因为需要修改外部传入的一级指针（使其指向 NULL）。

完整代码如下所示：

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

（2）底层原理

• 内存管理：释放通过 malloc 分配的堆内存，避免内存泄漏。
• 后序遍历特性：采用左→右→根的释放顺序，确保释放父节点前已释放所有子节点，防止子节点内存无法访问（悬空）。
• 指针安全：通过二级指针修改原指针为 NULL，避免外部继续使用已释放的内存地址。

（3）应用示例

假设已构建了如下的二叉树，并获取根节点指针：

// 构建简单二叉树
BTNode* root = buyNode('A');
root->left = buyNode('B');
root->right = buyNode('C');
root->left->left = buyNode('D');

销毁过程调用如下：

BinaryTreeDestory(&root);
// 销毁后 root 变为 NULL，避免野指针

销毁后，所有节点（A、B、C、D）的内存被释放，原根节点指针 root 被置为 NULL。

（4）执行流程

以上述过程为例，销毁步骤如下所示：

1. 调用 BinaryTreeDestory(&root)，*root 为节点 A（非空）。

2. 递归销毁左子树：BinaryTreeDestory(&(A->left))（处理节点 B）。

• 递归销毁 B 的左子树：BinaryTreeDestory(&(B->left))（处理节点 D）。
  • D 的左子树为 NULL → 直接返回；
  • D 的右子树为 NULL → 直接返回；
  • 释放节点 D 的内存，将 B->left 置为 NULL。
• 递归销毁 B 的右子树（NULL）→ 直接返回。
• 释放节点 B 的内存，将 A->left 置为 NULL。

3. 递归销毁右子树：BinaryTreeDestory(&(A->right))（处理节点 C）。

• C 的左子树为 NULL → 直接返回；
• C 的右子树为 NULL → 直接返回；
• 释放节点 C 的内存，将 A->right 置为 NULL。

4. 释放节点 A 的内存，将外部传入的 root 置为 NULL。

二、层序遍历

在前文中我们实现了先序遍历、中序遍历和后序遍历，这三种遍历方式被称为深度优先遍历。除此之外，我们还可以对二叉树进行广度优先遍历——层序遍历。

设二叉树的根节点所在的层数为1，则层序遍历就是从二叉树的根节点出发，首先访问第一层的树根结点，然后从左到右访问第二层上的结点，接着是第三层的结点，以此类推，自上而下、自左向右逐层访问树的结点的过程就是层序遍历。

要想实现层序遍历，我们还需要额外借助数据结构——队列。实现逻辑如下图所示：

我们将根节点保存在队列中，使得队列不为空。通过循环判断队列是否为空，如果不为空就取队头，将队头结点不为空的孩子结点入队列。

完整代码如下所示：

// 层序遍历---借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印队头
		BTNode* top = QueueFront(&q);
		printf("%c ", top->data);
		QueuePop(&q);
		//队头节点不为空的孩子节点入队列
		if (top->left)
			QueuePush(&q, top->left);
		if (top->right)
			QueuePush(&q, top->right);
	}

	QueueDesTroy(&q);
}

三、判断是否为完全二叉树

3.1 实现逻辑

要想实现对完全二叉树的判断，核心就是要关注下面两点：

（1）判断每层结点的个数；

（2）叶子结点是否从左向右依次排列。

该函数的核心逻辑是基于层序遍历（广度优先搜索）和队列辅助的：

• 初始化队列并将根节点入队。
• 层序遍历树：依次取出队头节点，若节点非空则将其左右孩子（无论是否为空）入队。
• 当首次遇到空节点（NULL）时，停止入队流程。
• 检查剩余队列：若剩余元素中存在非空节点，则不是完全二叉树；否则是完全二叉树。
• 最后销毁队列并返回结果。

画图分析如下：

对于非完全二叉树：

对于完全二叉树：

完整代码如下：

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//头节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空就直接出队列
			break;
		}
		//将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//不是完全二叉树
			QueueDesTroy(&q);
			return false;
		}
	}
	QueueDesTroy(&q);
	return true;
}

3.2 底层原理

• 完全二叉树特性：完全二叉树的节点按层序排列时，所有空节点（NULL）应集中在最后，且不存在 "空节点后出现非空节点" 的情况。
• 层序遍历优势：通过队列实现的层序遍历可按层次顺序访问节点，便于检测空节点的分布。
• 队列作用：暂存节点及其子节点（包括空节点），确保遍历顺序符合层次要求。

3.3 应用示例

完全二叉树示例：

        1
       / \
      2   3
     / \  /
    4  5 6

层序遍历入队序列（含空节点）：1,2,3,4,5,6,NULL,NULL,NULL,NULL,NULL。 首次遇到 NULL 后，剩余队列均为 NULL → 返回 true。

非完全二叉树示例：

        1
       / \
      2   3
       \
        5

层序遍历入队序列：1,2,3,NULL,5,NULL,NULL,NULL。 首次遇到 NULL 后，剩余队列中存在非空节点 5 → 返回 false。

3.4 执行逻辑

以完全二叉树示例为例，执行步骤如下：

1. 初始化队列，将根节点 1 入队 → 队列：[1]。

2. 第一层循环（遍历非空节点）：

• 取出 1，入队其左右孩子 2、3 → 队列：[2,3]
• 取出 2，入队其左右孩子 4、5 → 队列：[3,4,5]
• 取出 3，入队其左右孩子 6、NULL → 队列：[4,5,6,NULL]
• 取出 4，入队其左右孩子 NULL、NULL → 队列：[5,6,NULL,NULL,NULL]
• 取出 5，入队其左右孩子 NULL、NULL → 队列：[6,NULL,NULL,NULL,NULL,NULL]
• 取出 6，入队其左右孩子 NULL、NULL → 队列：[NULL,NULL,NULL,NULL,NULL,NULL,NULL]
• 取出 NULL，触发 break → 第一层循环结束

3. 第二层循环（检查剩余队列）：依次取出剩余元素，均为 NULL → 循环正常结束。

4. 销毁队列，返回 true。

总结

以上就是本期关于链式二叉树的实现的博客啦！下期博客博主将为大家带来二叉树的一些相关算法题详解，请大家多多关注哦！