二叉树在计算机科学中并非简单树结构的变体，而是一个严格定义的递归数据结构。其核心不在于“分枝”的形态，而在于其内在的逻辑约束和数学定义。理解二叉树，必须从其作为“有序树”的本质入手。
核心定义
* 二叉树是一个有限集合 K ，其结构满足以下递归定义：
* 空集条件：K可以是一个空集，称为空二叉树。
* 非空条件：若K非空，则它由一个称为根（Root）的节点r和两个互不相交的子集K1K_{1}K1 和K2K_{2}K2 组成，其中K1K_{1}K1 被定义为根节点的左子树，K2K_{2}K2 被定义为根节点的右子树，且K1K_{1}K1 和K2K_{2}K2 本身也必须是二叉树。
这一定义确立了二叉树的三个核心属性：
1. 最大度约束： 每个节点的度（子节点数）不能超过 2。
2. 有序性： 左右子树的顺序是绝对的，不可交换。这是二叉树与普通“度为2的树”最本质的区别。即使一个节点只有一个子节点，也必须明确指定它是左孩子还是右孩子。
3. 递归性： 树中的每一个节点，都可以看作是其子树的根，结构无限嵌套。
逻辑结构的五种基本形态
基于上述定义，二叉树在逻辑上可以归纳为五种基本形态，这涵盖了从空结构到满结构的所有可能性：
1. 空二叉树（无节点）
2. 仅含有根节点的二叉树
3. 根节点仅有左子树
4. 根节点仅有右子树
5. 根节点同时具有左子树和右子树
特殊形态的限定
在算法与数据结构的应用中，两类特殊的二叉树具有极其严格的定义，它们是理解堆、查找树等高级结构的基础。
* 满二叉树
深度为h的二叉树，若其节点数达到该深度下的最大值2h−12^h-12h−1,则称为满二叉树
* 定义特征： 除叶子节点外，每个节点的度均为 2。
* 层级特征： 所有叶子节点必须且只能出现在最底层（第h层）。
* 完全二叉树
深度为 h 的二叉树，若其节点数 n小于 2h−12^h-12h−1,但节点的排列顺序与同深度的满二叉树中编号为1至n的节点位置完全一致，则称为完全二叉树。
* 定义特征： 叶子节点只能出现在最下两层，且最下层的叶子节点必须集中在左侧连续位置。
* 结构推论： 若某节点只有单个孩子，则该孩子必为左孩子（不存在只有右孩子而无左孩子的情况）。
定义二叉树的代码实现
存储结构的逻辑映射
二叉树的定义直接决定了其在内存中的组织方式，主要分为顺序存储和链式存储两种逻辑模型。
1. 顺序存储（数组实现）
主要用于完全二叉树的存储。若将根节点存储在数组下标为 1 的位置，则对于任意下标为i的节点：
* 其左孩子节点的下标为2i2i2i
* 其右孩子节点的下标为2i+12i+12i+1
* 其双亲节点的下标为[i/2][i/2][i/2]
这种映射关系是二叉树定义在内存空间中的直接体现，利用了完全二叉树节点位置的规律性。
2. 链式存储（指针实现）
这是二叉树最通用的存储结构，定义了一个节点包含三个部分：
* 数据域：存储节点的值
* 左指针域：指向其左子树的根节点
* 右指针域：指向其右子树的根节点
这种结构通过指针显式地表达了二叉树定义中的“左、右子树”关系，是递归定义在内存中的物理实现。
遍历方式
二叉树的遍历并非仅仅是访问节点的顺序不同，其背后是函数调用栈对树结构进行深度优先搜索的数学投影。每一种遍历顺序都对应着根节点在递归三段论中的不同位置
先序遍历
先序遍历定义了根节点的优先访问权。对于任意子树，访问顺序严格遵循根节点 -> 左子树 -> 右子树。
* 数学表达： 设访问根节点的操作为V(r)V_{(r)}V(r) ,遍历左子树的操作为TleftT_{left}Tleft ,遍历右子树的操作为TrightT_{right}Tright ,则先序遍历的递归定义为：
> Preorder(T)=V(r)→Preorder(Tleft)→Preorder(Tright)\text{Preorder}(T) = V(r) \rightarrow \text{Preorder}(T_{\text{left}}) \rightarrow \text{Preorder}(T_{\text{right}})Preorder(T)=V(r)→Preorder(Tleft )→Preorder(Tright )
* 逻辑特征： 在递归下降的过程中，节点在被压入调用栈时即被访问。这使得先序遍历天然适合用于复制树结构、序列化树或建立前缀表达式。
中序遍历
中序遍历定义了根节点的中间位置，即左子树的完全展开必须先于根节点的访问。
* 数学表达： 对于任意非空节点，其左子树的所有节点必须先被访问，然后是根节点，最后是右子树：
> Inorder(T)=Inorder(Tleft)→V(r)→Inorder(Tright)\text{Inorder}(T) = \text{Inorder}(T_{\text{left}}) \rightarrow V(r) \rightarrow \text{Inorder}(T_{\text{right}})Inorder(T)=Inorder(Tleft )→V(r)→Inorder(Tright )
* 逻辑特征： 这种“左-根-右”的顺序在二叉搜索树中具有极高的价值，因为它能保证输出的节点值按升序排列。在递归实现中，这对应着函数在递归调用返回后、栈帧弹出前访问节点。
后序遍历
后序遍历强制根节点处于依赖链的末端，即必须先完全处理完左右子树，才能处理根节点。
* 数学表达： 访问顺序严格遵循：左子树 -> 右子树 -> 根节点。
> Postorder(T)=Postorder(Tleft)→Postorder(Tright)→V(r)\text{Postorder}(T) = \text{Postorder}(T_{\text{left}}) \rightarrow \text{Postorder}(T_{\text{right}}) \rightarrow V(r)Postorder(T)=Postorder(Tleft )→Postorder(Tright )→V(r)
* 逻辑特征： 在递归栈中，节点在栈帧即将弹出时才被访问。这使得后序遍历成为计算树高、释放内存（先删孩子再删根）以及生成后缀表达式的唯一选择。
对树的赋值和输出遍历
赋值
前序遍历
中序遍历
后序遍历
二叉搜索树的序关系定义
当我们在二叉树的基础上引入全序关系，它就进化为了二叉搜索树。这是一个基于比较的有序二叉树，其定义完全建立在节点值的大小关系上。
核心定义
对于树中的任意节点n,其左子树TleftT_{left}Tleft 和右子树TrightT_{right}Tright 必须满足以下序公理：
1. 左子树约束： 若x是TleftT_{left}Tleft 中的任意节点,则x.key≤n.keyx.key≤n.keyx.key≤n.key
> ∀x∈Tleft,x.key≤n.key\forall x \in T_{\text{left}}, \quad x.key \le n.key∀x∈Tleft ,x.key≤n.key
2. 右子树约束： 若y是TrightT_{right}Tright 中的任意节点,则x.key<n.keyx.key<n.keyx.key<n.key
> ∀y∈Tright,y.key>n.key\forall y \in T_{\text{right}}, \quad y.key > n.key∀y∈Tright ,y.key>n.key
旋转操作的代数意义
* 右旋 (Zig)： 用于修复左倾过度。设失衡节点为 PPP，其左孩子为 LLL，则右旋操作将LLL提升为新的子树根,PPP变为 LLL 的右孩子。
* 左旋 (Zag)： 用于修复右倾过度。设失衡节点为PPP，其右孩子为RRR，则左旋操作将RRR提升为新的子树根,PPP变为RRR的左孩子。
这些旋转操作构成了平衡二叉树自我调节的底层逻辑，确保了最坏情况下的O(logn)O(log_{ n})O(logn )性能保证
附:度为二的树和二叉树的区分
* 结构定义：度为2的树要求至少有一个结点的度为2（是“树”的一种），而二叉树是独立结构，要求每个结点的度不超过2（可以全是0或1）。
* 子树顺序：度为2的树不区分左右子树，位置互换不影响结构；而二叉树严格区分左右子树，左右互换即为新树。
总结
综上所述，二叉树的功能可以归结为：它是一种将“逻辑关系”转化为“物理结构”的工具。无论是决策逻辑、数据顺序、语法结构还是优先级规则，二叉树都提供了一种统一的、高效的计算框架，使得计算机能够以层级化的方式处理这些逻辑，从而极大地提升了算法的效率和可理解性。
（来自于我在网上查的资料+我自己的总结）
