二叉树的应用场景：

数据检索：二叉搜索树（BST）支持高效的查找、插入、删除（平衡 BST 如 AVL 树、红黑树进一步优化性能）。

排序与编码：堆（完全二叉树）用于优先队列和堆排序；哈夫曼树用于数据压缩（哈夫曼编码）。

数据库索引：B 树、B + 树（多叉树变种）是数据库索引的核心结构，本质是二叉树的扩展。

编译器优化：语法树（二叉树的一种）用于代码解析和优化。

二叉树基本构成

基本的二叉树构成如下图所示：

其中数据域包含灵活的数据类型，且Java并没有类似于C/C++一般的结构体类型，故通常使用类（Class）来进行声明。

还原二叉树

[二级题库] 设二叉树的前序序列是ABDEGHCFIJ，中序序列是DBGEHACIFJ。按照层次输出（从上到下，同一层从左到右）的序列为（）。

首先我们要明确前序和中序的遍历顺序

• 前序遍历的严格规则与核心性质

  • 遍历规则：对任意一棵二叉树，访问顺序为 访问根节点 → 递归前序遍历左子树 → 递归前序遍历右子树。

  • 核心性质：任意一棵子树的前序序列，第一个元素一定是该子树的根节点。

• 中序遍历的严格规则与核心性质

  • 遍历规则：对任意一棵二叉树，访问顺序为 递归中序遍历左子树 → 访问根节点 → 递归中序遍历右子树。

  • 核心性质：已知某子树的根节点，在该子树的中序序列中，根节点左侧的所有元素属于左子树，右侧的所有元素属于右子树。

依据以上性质正式开始推演：

1. 依据前序序列首位可知二叉树根节点为A

2. 依据中序序列，通过查找根节点位置获得左右子树遍历结果

   • 由中序序列得出：左序D B G E H （５位） 右序C I F J（４位）

   • 由前序序列得出：左序ＢＤＥＧＨ（５位）右序ＣＦＩＪ（４位）

     • 在本实例中我们仅推演左子树以做示范

     • 依据前序序列首位可知本次遍历的二叉树父节点为Ｂ

       • 复用上文逻辑可得左子树为Ｄ右子树为ＥＧＨ（前序）ＧＥＨ（中序）

       • 继续查找右子树　最终实现对整颗二叉树的遍历

二叉树基本声明

class TreeNode{
    int value; //数据域
    TreeNode left; //定义左子树
    TreeNode right; //定义右子树
    
    //构造方法
    public TreeNode(int value){
        this.value = value; //初始化节点值
        this.left = null; //左子树默认为空
        this.right = null; //右子树默认为空
    }
}