一、什么是二叉树二叉树Binary Tree是一种特殊的树结构它的每个节点最多有两个子节点分别称为左子节点和右子节点。二叉树的核心特点左右子树是有序的不可颠倒是计算机科学中最基础、应用最广泛的数据结构之一。二、二叉树的五种基本形态根据节点的有无二叉树可以分为五种基本形态空二叉树没有任何节点只有根节点只有一个根节点没有子节点根节点只有左子树根节点只有左子节点根节点只有右子树根节点只有右子节点完全二叉树除了最后一层其他层的节点数都达到最大值且最后一层的节点都靠左排列满二叉树所有节点都有 0 或 2 个子节点每一层的节点数都达到最大值。三、二叉树的节点定义二叉树的每个节点由三部分组成数据域存储节点的具体数据左子节点指针指向左子节点右子节点指针指向右子节点。对应的 C 语言代码定义如下// 二叉树节点结构体 typedef struct TreeNode { int val; // 数据域 struct TreeNode* left; // 左子节点指针 struct TreeNode* right; // 右子节点指针 } TreeNode;四、二叉树的四种遍历方式二叉树的遍历是指按照某种规则访问树中的所有节点且每个节点只访问一次。常见的遍历方式有四种1. 前序遍历根→左→右先访问根节点再递归遍历左子树最后递归遍历右子树。代码实现// 前序遍历 void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-val); // 先访问根节点 preorder(root-left); // 再遍历左子树 preorder(root-right); // 最后遍历右子树 }2. 中序遍历左→根→右先递归遍历左子树再访问根节点最后递归遍历右子树。代码实现// 中序遍历 void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); // 先遍历左子树 printf(%d , root-val); // 再访问根节点 inorder(root-right); // 最后遍历右子树 }3. 后序遍历左→右→根先递归遍历左子树再递归遍历右子树最后访问根节点。代码实现// 后序遍历 void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); // 先遍历左子树 postorder(root-right); // 再遍历右子树 printf(%d , root-val); // 最后访问根节点 }4. 层序遍历从上到下从左到右按照树的层次从上到下、从左到右依次访问每个节点也叫广度优先遍历BFS。代码实现使用队列辅助#include stdio.h #include stdlib.h // 层序遍历 void levelOrder(TreeNode* root) { if (root NULL) return; // 使用队列存储待访问的节点 TreeNode** queue (TreeNode**)malloc(sizeof(TreeNode*) * 100); int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode* node queue[front]; printf(%d , node-val); // 左子节点入队 if (node-left ! NULL) { queue[rear] node-left; } // 右子节点入队 if (node-right ! NULL) { queue[rear] node-right; } } free(queue);五、二叉树的基本操作1. 创建节点创建一个新的二叉树节点初始化数据和子节点指针// 创建新节点 TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; }2. 构建二叉树通过手动指定节点的父子关系构建一棵二叉树// 构建示例二叉树 TreeNode* buildTree() { // 创建节点 TreeNode* root createNode(1); TreeNode* node2 createNode(2); TreeNode* node3 createNode(3); TreeNode* node4 createNode(4); TreeNode* node5 createNode(5); TreeNode* node6 createNode(6); // 建立父子关系 root-left node2; root-right node3; node2-left node4; node2-right node5; node3-right node6; return root; }3. 计算树的高度树的高度是从根节点到最远叶子节点的路径长度代码实现// 计算树的高度 int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); return (leftHeight rightHeight ? leftHeight : rightHeight) 1; }4. 计算树的节点总数递归计算树的节点总数代码实现// 计算树的节点总数 int getNodeCount(TreeNode* root) { if (root NULL) return 0; return getNodeCount(root-left) getNodeCount(root-right) 1; }5. 释放树的内存递归释放树的所有节点内存避免内存泄漏// 释放树的内存 void freeTree(TreeNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); }六、完整代码示例#include stdio.h #include stdlib.h // 二叉树节点结构体 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建新节点 TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } // 构建示例二叉树 TreeNode* buildTree() { TreeNode* root createNode(1); TreeNode* node2 createNode(2); TreeNode* node3 createNode(3); TreeNode* node4 createNode(4); TreeNode* node5 createNode(5); TreeNode* node6 createNode(6); root-left node2; root-right node3; node2-left node4; node2-right node5; node3-right node6; return root; } // 前序遍历 void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-val); preorder(root-left); preorder(root-right); } // 中序遍历 void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); } // 后序遍历 void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-val); } // 层序遍历 void levelOrder(TreeNode* root) { if (root NULL) return; TreeNode** queue (TreeNode**)malloc(sizeof(TreeNode*) * 100); int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode* node queue[front]; printf(%d , node-val); if (node-left ! NULL) { queue[rear] node-left; } if (node-right ! NULL) { queue[rear] node-right; } } free(queue); } // 计算树的高度 int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); return (leftHeight rightHeight ? leftHeight : rightHeight) 1; } // 计算树的节点总数 int getNodeCount(TreeNode* root) { if (root NULL) return 0; return getNodeCount(root-left) getNodeCount(root-right) 1; } // 释放树的内存 void freeTree(TreeNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } int main() { // 构建二叉树 TreeNode* root buildTree(); // 测试前序遍历 printf(前序遍历); preorder(root); // 输出1 2 4 5 3 6 printf(\n); // 测试中序遍历 printf(中序遍历); inorder(root); // 输出4 2 5 1 3 6 printf(\n); // 测试后序遍历 printf(后序遍历); postorder(root); // 输出4 5 2 6 3 1 printf(\n); // 测试层序遍历 printf(层序遍历); levelOrder(root); // 输出1 2 3 4 5 6 printf(\n); // 测试树的高度 printf(树的高度%d\n, getHeight(root)); // 输出3 // 测试节点总数 printf(节点总数%d\n, getNodeCount(root)); // 输出6 // 释放内存 freeTree(root); printf(内存已释放\n); return 0; }七、二叉树的实际应用场景二叉树在实际开发中应用非常广泛常见场景包括文件系统操作系统的目录结构就是一棵树根目录是根节点子目录和文件是子节点DOM 树HTML 文档的结构就是一棵树根节点是html子节点是各种标签数据库索引MySQL 的 InnoDB 引擎使用 B 树作为索引结构提高查询效率路由表路由器的路由表使用前缀树Trie存储路由信息表达式求值算术表达式可以表示为一棵二叉树通过后序遍历计算结果哈夫曼树用于数据压缩根据字符出现频率构建最优编码。八、总结二叉树是一种特殊的树结构每个节点最多有两个子节点支持前序、中序、后序、层序四种遍历方式以及计算高度、节点总数等基本操作。二叉树是计算机科学的基石在实际开发中应用非常广泛是算法和开发中不可或缺的基础数据结构。希望这篇文章能帮助你深入理解二叉树的原理和实现 5.二叉树：计算机科学的基石
一、什么是二叉树二叉树Binary Tree是一种特殊的树结构它的每个节点最多有两个子节点分别称为左子节点和右子节点。二叉树的核心特点左右子树是有序的不可颠倒是计算机科学中最基础、应用最广泛的数据结构之一。二、二叉树的五种基本形态根据节点的有无二叉树可以分为五种基本形态空二叉树没有任何节点只有根节点只有一个根节点没有子节点根节点只有左子树根节点只有左子节点根节点只有右子树根节点只有右子节点完全二叉树除了最后一层其他层的节点数都达到最大值且最后一层的节点都靠左排列满二叉树所有节点都有 0 或 2 个子节点每一层的节点数都达到最大值。三、二叉树的节点定义二叉树的每个节点由三部分组成数据域存储节点的具体数据左子节点指针指向左子节点右子节点指针指向右子节点。对应的 C 语言代码定义如下// 二叉树节点结构体 typedef struct TreeNode { int val; // 数据域 struct TreeNode* left; // 左子节点指针 struct TreeNode* right; // 右子节点指针 } TreeNode;四、二叉树的四种遍历方式二叉树的遍历是指按照某种规则访问树中的所有节点且每个节点只访问一次。常见的遍历方式有四种1. 前序遍历根→左→右先访问根节点再递归遍历左子树最后递归遍历右子树。代码实现// 前序遍历 void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-val); // 先访问根节点 preorder(root-left); // 再遍历左子树 preorder(root-right); // 最后遍历右子树 }2. 中序遍历左→根→右先递归遍历左子树再访问根节点最后递归遍历右子树。代码实现// 中序遍历 void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); // 先遍历左子树 printf(%d , root-val); // 再访问根节点 inorder(root-right); // 最后遍历右子树 }3. 后序遍历左→右→根先递归遍历左子树再递归遍历右子树最后访问根节点。代码实现// 后序遍历 void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); // 先遍历左子树 postorder(root-right); // 再遍历右子树 printf(%d , root-val); // 最后访问根节点 }4. 层序遍历从上到下从左到右按照树的层次从上到下、从左到右依次访问每个节点也叫广度优先遍历BFS。代码实现使用队列辅助#include stdio.h #include stdlib.h // 层序遍历 void levelOrder(TreeNode* root) { if (root NULL) return; // 使用队列存储待访问的节点 TreeNode** queue (TreeNode**)malloc(sizeof(TreeNode*) * 100); int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode* node queue[front]; printf(%d , node-val); // 左子节点入队 if (node-left ! NULL) { queue[rear] node-left; } // 右子节点入队 if (node-right ! NULL) { queue[rear] node-right; } } free(queue);五、二叉树的基本操作1. 创建节点创建一个新的二叉树节点初始化数据和子节点指针// 创建新节点 TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; }2. 构建二叉树通过手动指定节点的父子关系构建一棵二叉树// 构建示例二叉树 TreeNode* buildTree() { // 创建节点 TreeNode* root createNode(1); TreeNode* node2 createNode(2); TreeNode* node3 createNode(3); TreeNode* node4 createNode(4); TreeNode* node5 createNode(5); TreeNode* node6 createNode(6); // 建立父子关系 root-left node2; root-right node3; node2-left node4; node2-right node5; node3-right node6; return root; }3. 计算树的高度树的高度是从根节点到最远叶子节点的路径长度代码实现// 计算树的高度 int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); return (leftHeight rightHeight ? leftHeight : rightHeight) 1; }4. 计算树的节点总数递归计算树的节点总数代码实现// 计算树的节点总数 int getNodeCount(TreeNode* root) { if (root NULL) return 0; return getNodeCount(root-left) getNodeCount(root-right) 1; }5. 释放树的内存递归释放树的所有节点内存避免内存泄漏// 释放树的内存 void freeTree(TreeNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); }六、完整代码示例#include stdio.h #include stdlib.h // 二叉树节点结构体 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建新节点 TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } // 构建示例二叉树 TreeNode* buildTree() { TreeNode* root createNode(1); TreeNode* node2 createNode(2); TreeNode* node3 createNode(3); TreeNode* node4 createNode(4); TreeNode* node5 createNode(5); TreeNode* node6 createNode(6); root-left node2; root-right node3; node2-left node4; node2-right node5; node3-right node6; return root; } // 前序遍历 void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-val); preorder(root-left); preorder(root-right); } // 中序遍历 void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); } // 后序遍历 void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-val); } // 层序遍历 void levelOrder(TreeNode* root) { if (root NULL) return; TreeNode** queue (TreeNode**)malloc(sizeof(TreeNode*) * 100); int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode* node queue[front]; printf(%d , node-val); if (node-left ! NULL) { queue[rear] node-left; } if (node-right ! NULL) { queue[rear] node-right; } } free(queue); } // 计算树的高度 int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); return (leftHeight rightHeight ? leftHeight : rightHeight) 1; } // 计算树的节点总数 int getNodeCount(TreeNode* root) { if (root NULL) return 0; return getNodeCount(root-left) getNodeCount(root-right) 1; } // 释放树的内存 void freeTree(TreeNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } int main() { // 构建二叉树 TreeNode* root buildTree(); // 测试前序遍历 printf(前序遍历); preorder(root); // 输出1 2 4 5 3 6 printf(\n); // 测试中序遍历 printf(中序遍历); inorder(root); // 输出4 2 5 1 3 6 printf(\n); // 测试后序遍历 printf(后序遍历); postorder(root); // 输出4 5 2 6 3 1 printf(\n); // 测试层序遍历 printf(层序遍历); levelOrder(root); // 输出1 2 3 4 5 6 printf(\n); // 测试树的高度 printf(树的高度%d\n, getHeight(root)); // 输出3 // 测试节点总数 printf(节点总数%d\n, getNodeCount(root)); // 输出6 // 释放内存 freeTree(root); printf(内存已释放\n); return 0; }七、二叉树的实际应用场景二叉树在实际开发中应用非常广泛常见场景包括文件系统操作系统的目录结构就是一棵树根目录是根节点子目录和文件是子节点DOM 树HTML 文档的结构就是一棵树根节点是html子节点是各种标签数据库索引MySQL 的 InnoDB 引擎使用 B 树作为索引结构提高查询效率路由表路由器的路由表使用前缀树Trie存储路由信息表达式求值算术表达式可以表示为一棵二叉树通过后序遍历计算结果哈夫曼树用于数据压缩根据字符出现频率构建最优编码。八、总结二叉树是一种特殊的树结构每个节点最多有两个子节点支持前序、中序、后序、层序四种遍历方式以及计算高度、节点总数等基本操作。二叉树是计算机科学的基石在实际开发中应用非常广泛是算法和开发中不可或缺的基础数据结构。希望这篇文章能帮助你深入理解二叉树的原理和实现