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

节点设计：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;}