数据结构篇（八）——二叉树

在计算机科学中，二叉树（Binary Tree）是最基础也是最核心的数据结构之一。无论是数据库的索引（B+树）、编译器的语法分析（语法树）、还是搜索引擎的排序（堆排序），背后都离不开二叉树的影子。

简单来说，二叉树是一种每个节点最多只有两个子节点的树形结构。这个"最多两个"的限制看似简单，却衍生出了无数精妙的算法和数据结构——二叉搜索树、平衡二叉树、堆、哈夫曼树、红黑树……掌握二叉树，就等于拿到了打开数据结构和算法大门的钥匙。

本文将从零开始，用C 语言带你逐步实现一个完整的二叉树，涵盖定义、创建、遍历、查找、销毁等操作，代码按照功能拆分为独立的模块，方便理解和复用。

目录

一、基本概念

1.二叉树的五种基本形态

二、二叉树的性质

1.完全二叉树和满二叉树的区分

1. 满二叉树

2. 完全二叉树

三、二叉树的存储结构

1. 顺序存储（数组）

2. 链式存储（指针）

四、代码模块实现

1.创建节点

2.插入节点（构建二叉树）

3.前序遍历（Preorder）

4.中序遍历（Inorder）

5.后序遍历（Postorder）

6.层序遍历（Level Order）

7.获取树的节点个数

8.获取树的深度（高度）

9.查找节点

10.销毁二叉树（释放内存）

五、代码测试

六、完整程序运行效果

一、基本概念

在进入代码之前，先理清二叉树中的几个核心术语：

1.二叉树的五种基本形态

空二叉树 只有根节点 只有左子树 只有右子树 左右子树齐全 ∅ A A A A \ / / \ B B B C

二、二叉树的性质

1.第 i 层最多有 2^(i-1) 个节点（i ≥ 1） 2.深度为 k 的二叉树最多有 2^k - 1 个节点 3.叶子节点数 = 度为 2 的节点数 + 1（记作 n₀ = n₂ + 1） 4.完全二叉树：除了最后一层，其他层都满，且最后一层的节点靠左排列 5.满二叉树：所有层的节点数都达到最大值 6.任意二叉树，度为 0 的叶子个数比度为 2 的节点个数多 1 应用： 具有 2n 个结点的完全二叉树，叶子节点个数为 n 假设 度为 0 → N0 个 度为 1 → N1 个 度为 2 → N2 个 N0 = N2+1 → N2 = N0-1 则 N0 + N1 + N0 -1 = 2n 完全二叉树中度为 1 的节点个数为 0 或 1 又因为有 2n 个节点 (偶数个) 2N0+N1-1=2n N1 只能为 1 ∴ N0 = n

1.完全二叉树和满二叉树的区分

1. 满二叉树

除叶子结点（度 0）外，其余所有节点同时拥有左孩子、右孩子；

每一层节点数量都达到该层最大容量，没有空位。

高度为 h 的满二叉树，总节点数：2^(h-1)

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

2. 完全二叉树

按从上到下、从左往右顺序填满节点； 最后一层可以不满，但是节点必须靠左紧密连续排布，不允许出现右侧有节点、左侧空缺。

(1) / \ (2) (3) / \ / (4) (5) (6)

三、二叉树的存储结构

二叉树有两种存储方式：

1. 顺序存储（数组）

适用于完全二叉树。将节点按层序放入数组，节点 i 的左孩子下标为2i+1，右孩子为2i+2。

A(0) / \ B(1) C(2) / \ \ D(3) E(4) F(5) 数组：[A, B, C, D, E, F]

缺点：非完全二叉树会浪费大量空间。

2. 链式存储（指针）

每个节点包含三部分：数据域 + 左孩子指针 + 右孩子指针。这是最常用的方式，本文采用这种方案。

结构定义如下：

// 模块1：二叉树的节点结构定义 typedef struct TreeNode { int data; // 数据域（这里用 int，可替换为任意类型） struct TreeNode *left; // 左孩子指针 struct TreeNode *right;// 右孩子指针 } TreeNode;

四、代码模块实现

1.创建节点

创建单个节点，分配内存并初始化。

TreeNode* createNode(int data) { TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode)); if (newNode == NULL) { printf("内存分配失败！\n"); exit(1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; }

2.插入节点（构建二叉树）

/** * 按层序构建二叉树 * @param arr 包含节点数据的数组（-1 表示空节点） * @param size 数组长度 * @param index 当前处理的数组下标 * @return 构建完成的树的根节点 */ TreeNode* buildTree(int arr[], int size, int index) { if (index >= size || arr[index] == -1) { return NULL; } TreeNode *root = createNode(arr[index]); // 递归构建左子树（下标 2*index+1） root->left = buildTree(arr, size, 2 * index + 1); // 递归构建右子树（下标 2*index+2） root->right = buildTree(arr, size, 2 * index + 2); return root; }

示例：数组 {1, 2, 3, 4, 5, -1, 6} 构建的二叉树：

1 / \ 2 3 / \ \ 4 5 6

3.前序遍历（Preorder）

顺序：根节点 → 左子树 → 右子树

/** * 前序遍历二叉树（递归版） * 顺序：根 -> 左 -> 右 * @param root 二叉树根节点 */ void preorderTraversal(TreeNode *root) { if (root == NULL) { return; } printf("%d ", root->data); // 1. 访问根节点 preorderTraversal(root->left); // 2. 遍历左子树 preorderTraversal(root->right); // 3. 遍历右子树 }

4.中序遍历（Inorder）

顺序：左子树 → 根节点 → 右子树

/** * 中序遍历二叉树（递归版） * 顺序：左 -> 根 -> 右 * @param root 二叉树根节点 */ void inorderTraversal(TreeNode *root) { if (root == NULL) { return; } inorderTraversal(root->left); // 1. 遍历左子树 printf("%d ", root->data); // 2. 访问根节点 inorderTraversal(root->right); // 3. 遍历右子树 }

5.后序遍历（Postorder）

顺序：左子树 → 右子树 → 根节点

/** * 后序遍历二叉树（递归版） * 顺序：左 -> 右 -> 根 * @param root 二叉树根节点 */ void postorderTraversal(TreeNode *root) { if (root == NULL) { return; } postorderTraversal(root->left); // 1. 遍历左子树 postorderTraversal(root->right); // 2. 遍历右子树 printf("%d ", root->data); // 3. 访问根节点 }

三种递归遍历的记忆口诀：

• 前序：根左右
• 中序：左根右
• 后序：左右根

6.层序遍历（Level Order）

顺序：从上到下、从左到右，逐层访问。

需要借助队列来实现，这里我们实现一个简单队列配合使用。

// ---------- 辅助：简单队列结构 ---------- #define MAX_QUEUE_SIZE 100 typedef struct Queue { TreeNode *data[MAX_QUEUE_SIZE]; int front; int rear; } Queue; void initQueue(Queue *q) { q->front = 0; q->rear = 0; } void enqueue(Queue *q, TreeNode *node) { if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) { printf("队列已满！\n"); return; } q->data[q->rear] = node; q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; } TreeNode* dequeue(Queue *q) { if (q->front == q->rear) { return NULL; } TreeNode *node = q->data[q->front]; q->front = (q->front + 1) % MAX_QUEUE_SIZE; return node; } int isQueueEmpty(Queue *q) { return q->front == q->rear; } // ---------- 层序遍历 ---------- /** * 层序遍历二叉树（借助队列） * 顺序：逐层从左到右 * @param root 二叉树根节点 */ void levelOrderTraversal(TreeNode *root) { if (root == NULL) { return; } Queue q; initQueue(&q); enqueue(&q, root); while (!isQueueEmpty(&q)) { TreeNode *current = dequeue(&q); printf("%d ", current->data); if (current->left != NULL) { enqueue(&q, current->left); } if (current->right != NULL) { enqueue(&q, current->right); } } }

7.获取树的节点个数

/** * 计算二叉树中节点的个数 * 公式：左子树节点数 + 右子树节点数 + 1（根） * @param root 二叉树根节点 * @return 节点总数 */ int getNodeCount(TreeNode *root) { if (root == NULL) { return 0; } return getNodeCount(root->left) + getNodeCount(root->right) + 1; }

8.获取树的深度（高度）

/** * 计算二叉树的高度（深度） * 公式：max(左子树高度, 右子树高度) + 1 * @param root 二叉树根节点 * @return 树的高度 */ int getTreeHeight(TreeNode *root) { if (root == NULL) { return 0; } int leftHeight = getTreeHeight(root->left); int rightHeight = getTreeHeight(root->right); return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; }

9.查找节点

/** * 在二叉树中查找值为 target 的节点 * @param root 二叉树根节点 * @param target 要查找的目标值 * @return 找到返回指向该节点的指针，否则返回 NULL */ TreeNode* searchNode(TreeNode *root, int target) { if (root == NULL) { return NULL; } if (root->data == target) { return root; } // 先在左子树找 TreeNode *found = searchNode(root->left, target); if (found != NULL) { return found; } // 左子树没找到，再去右子树找 return searchNode(root->right, target); }

10.销毁二叉树（释放内存）

/** * 销毁整棵二叉树，释放所有节点内存 * 使用后序遍历：先释放子树，再释放根 * @param root 二叉树根节点（二级指针，释放后置 NULL） */ void destroyTree(TreeNode **root) { if (*root == NULL) { return; } destroyTree(&((*root)->left)); // 1. 释放左子树 destroyTree(&((*root)->right)); // 2. 释放右子树 free(*root); // 3. 释放当前节点 *root = NULL; // 4. 指针置空，防止野指针 }

为什么用二级指针？因为我们需要在函数内部修改调用方的root指针，将其置为 NULL。如果只传一级指针，函数内修改的是指针的副本，调用方的指针仍是野指针。

五、代码测试

#include <stdio.h> #include <stdlib.h> // 在此处粘贴上述所有模块代码 ... int main() { // 用数组构建一棵二叉树 // 树结构： // 1 // / \ // 2 3 // / \ \ // 4 5 6 int arr[] = {1, 2, 3, 4, 5, -1, 6}; int size = sizeof(arr) / sizeof(arr[0]); TreeNode *root = buildTree(arr, size, 0); printf("===== 二叉树的遍历 =====\n"); printf("前序遍历："); preorderTraversal(root); printf("\n"); printf("中序遍历："); inorderTraversal(root); printf("\n"); printf("后序遍历："); postorderTraversal(root); printf("\n"); printf("层序遍历："); levelOrderTraversal(root); printf("\n\n"); printf("===== 树的基本信息 =====\n"); printf("节点个数：%d\n", getNodeCount(root)); printf("树的高度：%d\n\n", getTreeHeight(root)); printf("===== 查找节点 =====\n"); int target = 5; TreeNode *found = searchNode(root, target); if (found != NULL) { printf("找到节点：%d\n\n", found->data); } else { printf("未找到节点：%d\n\n", target); } // 释放内存 destroyTree(&root); if (root == NULL) { printf("二叉树已成功销毁！\n"); } return 0; }

六、完整程序运行效果

===== 二叉树的遍历 ===== 前序遍历：1 2 4 5 3 6 中序遍历：4 2 5 1 3 6 后序遍历：4 5 2 6 3 1 层序遍历：1 2 3 4 5 6 ===== 树的基本信息 ===== 节点个数：6 树的高度：3 ===== 查找节点 ===== 找到节点：5 二叉树已成功销毁！

总结：

本文梳理了二叉树基础理论与链式二叉树全套代码实现。遍历是二叉树核心，熟练掌握本节内容，可为后续学习高阶树形结构打下基础。