二叉树的性质、定义与链式存储实现
前言：今天我们来深入学习数据结构中的重要概念——二叉树。作为树形结构中最基础也是最重要的类型，二叉树在计算机科学中有着广泛的应用。本文将从基本概念出发，重点讲解二叉树的链式存储实现。
一、什么是二叉树？
1.1 二叉树的定义
二叉树是每个节点最多有两个子树的有序树，通常子树被称作"左子树"和"右子树"。
特点：
- 每个节点最多有两个子节点（度≤2）
- 子树有左右之分，次序不能颠倒
- 二叉树可以是空树，也可以是由根节点和左右子树组成
1.2 二叉树的基本性质
性质1：在二叉树的第i层上最多有2^(i-1)个节点（i≥1）
性质2：深度为k的二叉树最多有2^k - 1个节点（k≥1）
性质3：对于任何一棵二叉树，如果其终端节点数为n₀，度为2的节点数为n₂，则n₀ = n₂ + 1
性质4：具有n个节点的完全二叉树的深度为⌊log₂n⌋ + 1
二、二叉树的存储表示
2.1 顺序存储结构
顺序存储适用于完全二叉树，使用数组来存储节点：
// 顺序存储示例（仅展示概念）// 节点i的左孩子：2i，右孩子：2i+1，父节点：i/2// 数组索引：[0, 1, 2, 3, 4, 5, 6, 7]// 对应节点：[A, B, C, D, E, F, G, H]优点：
- 存储空间利用率高
- 节点关系明确，通过下标计算即可获得父子关系
缺点：
- 对于非完全二叉树，空间浪费严重
- 插入、删除操作不方便
2.2 链式存储结构（重点！）
链式存储是二叉树最常用的存储方式，每个节点包含数据域和指向左右孩子的指针域。
三、二叉树链式存储的Java实现
下面我们来看完整的链式存储实现：
packagechapter4;publicclassBiTree{BiTreeNoderoot;// 根节点intnum;// 节点总数publicBiTree(){root=newBiTreeNode();num=0;}privateintpi=0;// 创建二叉树的公共接口publicvoidcreateBiTree(Stringinput){pi=0;// 重置位置指针root=createBiTreeHelper(input);num=countNodes(root);// 统计节点数}// 递归创建二叉树的辅助方法privateBiTreeNodecreateBiTreeHelper(Stringinput){if(pi>=input.length()||input.charAt(pi)=='#'){pi++;// 跳过'#'returnnull;// 空节点}// 创建当前节点BiTreeNoderoot=newBiTreeNode(input.charAt(pi));pi++;// 移动到下一个字符// 递归创建左子树root.lchild=createBiTreeHelper(input);// 递归创建右子树root.rchild=createBiTreeHelper(input);returnroot;}// 计算节点总数的递归方法privateintcountNodes(BiTreeNoderoot){if(root==null){return0;}// 1（当前节点） + 左子树节点数 + 右子树节点数return1+countNodes(root.lchild)+countNodes(root.rchild);}}// 二叉树节点类classBiTreeNode{chardata;// 数据域BiTreeNodelchild;// 左孩子指针BiTreeNoderchild;// 右孩子指针// 无参构造函数publicBiTreeNode(){}// 带数据的构造函数publicBiTreeNode(chardata){this.data=data;lchild=null;rchild=null;}// 完整构造函数publicBiTreeNode(chardata,BiTreeNodelchild,BiTreeNoderchild){this.data=data;this.lchild=lchild;this.rchild=rchild;}}代码详解
3.1 核心设计思想
- 节点设计：
BiTreeNode类采用经典的"数据域 + 左孩子 + 右孩子"三要素设计 - 递归创建：使用先序遍历的思想递归构建二叉树
- 空节点标记：使用’#'字符表示空节点，这是二叉树序列化的常用技巧
3.2 关键方法解析
createBiTreeHelper方法解析：
privateBiTreeNodecreateBiTreeHelper(Stringinput){if(pi>=input.length()||input.charAt(pi)=='#'){pi++;// 别忘了移动指针！returnnull;}BiTreeNoderoot=newBiTreeNode(input.charAt(pi));pi++;// 处理完当前字符后移动// 先序遍历：根 → 左 → 右root.lchild=createBiTreeHelper(input);root.rchild=createBiTreeHelper(input);returnroot;}输入示例：对于字符串 “ABD##E##CF##G##”
- A：根节点
- B：A的左孩子
- D：B的左孩子
- ##：D的左右孩子都为空
- E：B的右孩子
- ##：E的左右孩子都为空
- 以此类推…
3.3 技术亮点
- 递归思想：整个创建过程体现了递归的优雅
- 边界处理：正确处理了空节点和越界情况
- 节点统计：通过递归精确计算节点总数
- 封装设计：将递归细节封装在私有方法中，提供简洁的公共接口
四、应用场景
这种链式存储实现适用于：
- 表达式树的构建和计算
- 哈夫曼树的构造
- 二叉搜索树的操作
- AVL树、红黑树等平衡树的实现
五、总结
通过本文的学习，我们掌握了：
- 二叉树的基本性质和定义
- 顺序存储与链式存储的对比
- 链式存储的完整Java实现
- 递归创建二叉树的核心技巧
二叉树的链式存储虽然需要额外的指针空间，但其灵活性和操作便利性使其成为实际应用中的首选存储方式。
💪学习建议：动手实现这个代码，尝试不同的输入字符串，观察二叉树的构建过程。理解递归在树结构中的重要作用，这将为后续学习更复杂的树形结构打下坚实基础！
下期预告：二叉树的便利
如果觉得本文对你有帮助，别忘了点赞👍收藏❤️关注哦！有什么问题欢迎在评论区讨论交流！