《Java数据结构与算法》第四篇（二）二叉树的性质、定义与链式存储实现

二叉树的性质、定义与链式存储实现

前言：今天我们来深入学习数据结构中的重要概念——二叉树。作为树形结构中最基础也是最重要的类型，二叉树在计算机科学中有着广泛的应用。本文将从基本概念出发，重点讲解二叉树的链式存储实现。

一、什么是二叉树？

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 核心设计思想

1. 节点设计：BiTreeNode类采用经典的"数据域 + 左孩子 + 右孩子"三要素设计
2. 递归创建：使用先序遍历的思想递归构建二叉树
3. 空节点标记：使用’#'字符表示空节点，这是二叉树序列化的常用技巧

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 技术亮点

1. 递归思想：整个创建过程体现了递归的优雅
2. 边界处理：正确处理了空节点和越界情况
3. 节点统计：通过递归精确计算节点总数
4. 封装设计：将递归细节封装在私有方法中，提供简洁的公共接口

四、应用场景

这种链式存储实现适用于：

• 表达式树的构建和计算
• 哈夫曼树的构造
• 二叉搜索树的操作
• AVL树、红黑树等平衡树的实现

五、总结

通过本文的学习，我们掌握了：

1. 二叉树的基本性质和定义
2. 顺序存储与链式存储的对比
3. 链式存储的完整Java实现
4. 递归创建二叉树的核心技巧

二叉树的链式存储虽然需要额外的指针空间，但其灵活性和操作便利性使其成为实际应用中的首选存储方式。

💪学习建议：动手实现这个代码，尝试不同的输入字符串，观察二叉树的构建过程。理解递归在树结构中的重要作用，这将为后续学习更复杂的树形结构打下坚实基础！
下期预告：二叉树的便利

如果觉得本文对你有帮助，别忘了点赞👍收藏❤️关注哦！有什么问题欢迎在评论区讨论交流！