二叉树的定义

二叉树是一种具有特殊结构的树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。它可以为空（即没有节点），或者由一个根节点及两棵不相交的子树组成，这两棵子树分别称为左子树和右子树。

数学上，二叉树的递归定义如下：

• 空树是一棵二叉树。
• 若左子树和右子树均为二叉树，则一个根节点加上其左子树和右子树构成一棵二叉树。

二叉树的基本性质

二叉树的性质可以从其定义出发进行推导，以下是几类重要的性质：

性质1：二叉树第i层上的最大节点数

对于非空二叉树，第i层的最大节点数为2^(i-1)，其中i≥1。

性质2：深度为k的二叉树的最大节点数

深度为k的二叉树最多具有2^k - 1个节点（其中k≥1）。

性质3：二叉树的节点数与最小深度的关系

对于具有n个节点的二叉树，其最小深度为?log?n? + 1。

性质4：满二叉树的性质

满二叉树是指所有非叶子节点均有两个子节点，且所有叶子节点位于同一层的二叉树。满二叉树的节点数n与深度k的关系为n = 2^k - 1。

性质5：完全二叉树的性质

完全二叉树是指除最后一层外，其余层的节点数均达到最大值，且最后一层的节点尽可能靠左排列的二叉树。完全二叉树适合用数组存储，其节点编号规则如下：

• 根节点编号为1。
• 对于节点i，其左子节点编号为2i，右子节点编号为2i+1（如果存在）。

二叉树的存储结构

二叉树的存储结构通常分为链式存储和顺序存储两种形式：

链式存储

链式存储通过节点结构体或类来表示，每个节点包含数据域和指向左右子树的指针：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

顺序存储

顺序存储适用于完全二叉树或满二叉树，通过数组下标关系表示节点间的父子关系：

• 节点i的左子节点位于2i。
• 节点i的右子节点位于2i+1。

二叉树的遍历方式

二叉树的遍历是指按照某种顺序访问树中的所有节点，常见的遍历方式包括：

前序遍历

访问顺序：根节点 → 左子树 → 右子树。

中序遍历

访问顺序：左子树 → 根节点 → 右子树。

后序遍历

访问顺序：左子树 → 右子树 → 根节点。

层序遍历

按层级从上至下、从左至右依次访问节点，通常借助队列实现。

特殊二叉树类型

二叉搜索树（BST）

二叉搜索树是一种有序二叉树，其中每个节点的左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值。

平衡二叉树（AVL树）

平衡二叉树是一种高度平衡的二叉搜索树，其中任意节点的左右子树高度差不超过1，确保查找效率维持在O(log n)。

堆

堆是一种特殊的完全二叉树，满足堆序性质（如最大堆中父节点值大于或等于子节点值）。

二叉树的应用

二叉树广泛应用于计算机科学的多个领域：

• 二叉搜索树用于高效的数据检索。
• 堆用于优先队列的实现。
• 表达式树用于编译器的语法分析。
• 哈夫曼树用于数据压缩算法。

通过深入理解二叉树的定义和性质，可以更高效地设计算法和优化数据结构应用。