在计算机科学中二叉树Binary Tree是最基础也是最核心的数据结构之一。无论是数据库的索引B树、编译器的语法分析语法树、还是搜索引擎的排序堆排序背后都离不开二叉树的影子。简单来说二叉树是一种每个节点最多只有两个子节点的树形结构。这个最多两个的限制看似简单却衍生出了无数精妙的算法和数据结构——二叉搜索树、平衡二叉树、堆、哈夫曼树、红黑树……掌握二叉树就等于拿到了打开数据结构和算法大门的钥匙。本文将从零开始用C 语言带你逐步实现一个完整的二叉树涵盖定义、创建、遍历、查找、销毁等操作代码按照功能拆分为独立的模块方便理解和复用。目录一、基本概念1.二叉树的五种基本形态二、二叉树的性质1.完全二叉树和满二叉树的区分1. 满二叉树2. 完全二叉树三、二叉树的存储结构1. 顺序存储数组2. 链式存储指针四、代码模块实现1.创建节点2.插入节点构建二叉树3.前序遍历Preorder4.中序遍历Inorder5.后序遍历Postorder6.层序遍历Level Order7.获取树的节点个数8.获取树的深度高度9.查找节点10.销毁二叉树释放内存五、代码测试六、完整程序运行效果一、基本概念在进入代码之前先理清二叉树中的几个核心术语术语英文含义节点Node树中的基本单元存储数据和指向子节点的指针根节点Root树的最顶层节点没有父节点左/右孩子Left/Right Child一个节点的左/右子节点父节点Parent指向当前节点的上层节点叶子节点Leaf没有子节点的节点子树Subtree树中任何一个节点及其后代构成的局部树深度Depth从根节点到当前节点的边数高度Height从当前节点到最远叶子节点的边数层Level根节点在第 1 层其孩子在第 2 层以此类推节点的度Degree一个节点拥有的子节点个数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 N21 → N2 N0-1 则 N0 N1 N0 -1 2n 完全二叉树中度为 1 的节点个数为 0 或 1 又因为有 2n 个节点 (偶数个) 2N0N1-12n N1 只能为 1 ∴ N0 n1.完全二叉树和满二叉树的区分1. 满二叉树除叶子结点度 0外其余所有节点同时拥有左孩子、右孩子每一层节点数量都达到该层最大容量没有空位。高度为 h 的满二叉树总节点数2^(h-1)(1) / \ (2) (3) / \ / \ (4) (5) (6) (7)2. 完全二叉树按从上到下、从左往右顺序填满节点 最后一层可以不满但是节点必须靠左紧密连续排布不允许出现右侧有节点、左侧空缺。(1) / \ (2) (3) / \ / (4) (5) (6)三、二叉树的存储结构二叉树有两种存储方式1. 顺序存储数组适用于完全二叉树。将节点按层序放入数组节点 i 的左孩子下标为2i1右孩子为2i2。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*index1 root-left buildTree(arr, size, 2 * index 1); // 递归构建右子树下标 2*index2 root-right buildTree(arr, size, 2 * index 2); return root; }示例数组 {1, 2, 3, 4, 5, -1, 6} 构建的二叉树1 / \ 2 3 / \ \ 4 5 63.前序遍历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 二叉树已成功销毁总结本文梳理了二叉树基础理论与链式二叉树全套代码实现。遍历是二叉树核心熟练掌握本节内容可为后续学习高阶树形结构打下基础。
数据结构篇（八）——二叉树
在计算机科学中二叉树Binary Tree是最基础也是最核心的数据结构之一。无论是数据库的索引B树、编译器的语法分析语法树、还是搜索引擎的排序堆排序背后都离不开二叉树的影子。简单来说二叉树是一种每个节点最多只有两个子节点的树形结构。这个最多两个的限制看似简单却衍生出了无数精妙的算法和数据结构——二叉搜索树、平衡二叉树、堆、哈夫曼树、红黑树……掌握二叉树就等于拿到了打开数据结构和算法大门的钥匙。本文将从零开始用C 语言带你逐步实现一个完整的二叉树涵盖定义、创建、遍历、查找、销毁等操作代码按照功能拆分为独立的模块方便理解和复用。目录一、基本概念1.二叉树的五种基本形态二、二叉树的性质1.完全二叉树和满二叉树的区分1. 满二叉树2. 完全二叉树三、二叉树的存储结构1. 顺序存储数组2. 链式存储指针四、代码模块实现1.创建节点2.插入节点构建二叉树3.前序遍历Preorder4.中序遍历Inorder5.后序遍历Postorder6.层序遍历Level Order7.获取树的节点个数8.获取树的深度高度9.查找节点10.销毁二叉树释放内存五、代码测试六、完整程序运行效果一、基本概念在进入代码之前先理清二叉树中的几个核心术语术语英文含义节点Node树中的基本单元存储数据和指向子节点的指针根节点Root树的最顶层节点没有父节点左/右孩子Left/Right Child一个节点的左/右子节点父节点Parent指向当前节点的上层节点叶子节点Leaf没有子节点的节点子树Subtree树中任何一个节点及其后代构成的局部树深度Depth从根节点到当前节点的边数高度Height从当前节点到最远叶子节点的边数层Level根节点在第 1 层其孩子在第 2 层以此类推节点的度Degree一个节点拥有的子节点个数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 N21 → N2 N0-1 则 N0 N1 N0 -1 2n 完全二叉树中度为 1 的节点个数为 0 或 1 又因为有 2n 个节点 (偶数个) 2N0N1-12n N1 只能为 1 ∴ N0 n1.完全二叉树和满二叉树的区分1. 满二叉树除叶子结点度 0外其余所有节点同时拥有左孩子、右孩子每一层节点数量都达到该层最大容量没有空位。高度为 h 的满二叉树总节点数2^(h-1)(1) / \ (2) (3) / \ / \ (4) (5) (6) (7)2. 完全二叉树按从上到下、从左往右顺序填满节点 最后一层可以不满但是节点必须靠左紧密连续排布不允许出现右侧有节点、左侧空缺。(1) / \ (2) (3) / \ / (4) (5) (6)三、二叉树的存储结构二叉树有两种存储方式1. 顺序存储数组适用于完全二叉树。将节点按层序放入数组节点 i 的左孩子下标为2i1右孩子为2i2。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*index1 root-left buildTree(arr, size, 2 * index 1); // 递归构建右子树下标 2*index2 root-right buildTree(arr, size, 2 * index 2); return root; }示例数组 {1, 2, 3, 4, 5, -1, 6} 构建的二叉树1 / \ 2 3 / \ \ 4 5 63.前序遍历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 二叉树已成功销毁总结本文梳理了二叉树基础理论与链式二叉树全套代码实现。遍历是二叉树核心熟练掌握本节内容可为后续学习高阶树形结构打下基础。
