目录
性质一：在非空二叉树中，第i层上至多有2i-1个节点(i≧1)
性质三: 对于任何一棵二叉树，若度为2的节点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的节点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。
满二叉树：一棵深度为k 且有2k -1个节点的二叉树。（特点：每层都“充满”了节点）
完全二叉树：深度为k 的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k 的满二叉树中编号从1至n的节点一一对应
一、二叉树的性质
性质一：在非空二叉树中，第i层上至多有2i-1个节点(i≧1)
证明：用数学归纳法
当i=1时：只有一个根节点，21-1=20 =1，命题成立。 现假设对i>1时，处在第i-1层上至多有2(i-1)-1个节点。 由归纳假设知，第i-1层上至多有2i-2个节点。由于二叉树每个节点的度最大为2，故在第i层上最大节点数为第i-1层上最大节点数的2倍。 即 2×2i-2＝2i-1
第i层上至少有 1个节点
性质二：深度为k的二叉树至多有2^k-1个节点（k≧1)
证明：深度为k的二叉树的最大的节点数为二叉树中每层上的最大节点数之和。
由性质1知，二叉树的第1层、第2层⋯第k层上的节点数至多有： 2^0、2^1 …2^k-1 。 ∴ 总的节点数至多有： 2^0+2^1+ …+2^k-1=2^k-1
深度为k时至少有 个节点
性质三: 对于任何一棵二叉树，若度为2的节点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）
性质4: 具有n个节点的完全二叉树的深度必为
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的节点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。
二、特殊形态的二叉树
满二叉树：一棵深度为k 且有2k -1个节点的二叉树。（特点：每层都“充满”了节点）
1. 定义与性质
节点结构：
每个非叶子节点都有恰好两个子节点（左和右）。
所有叶子节点都位于树的，最后一层，且该层无空缺。
数学关系：
深度为 (k) 的满二叉树，总节点数为
第 (i) 层的节点数为 。
高度平衡：
所有叶子节点到根节点的路径长度相同。
完全二叉树：深度为k 的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k 的满二叉树中编号从1至n的节点一一对应
最后一层节点有缺失，缺失部分为同层右侧
定义与性质
节点填充规则：
除最后一层外，其他层必须完全填满。
最后一层的节点必须从左到右连续填充。
数学关系：
深度为 (k) 的完全二叉树，总节点数 (n) 满足 (2^{k-1} \leq n \leq 2^k -1\)。
高效存储：
可用数组存储，节点索引关系：
左子节点：(2i + 1)
右子节点：(2i + 2)
父节点：(\lfloor \frac{i-1}{2} \rfloor\)
满二叉树和完全二叉树的区别
满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个节点。满二叉树是完全二叉树的一个特例。
三、二叉树的存储结构
（一）、二叉树的顺序存储
实现：按满二叉树的节点层次编号，依次存放二叉树中的数据元素。
判断双亲所在位置：
向下取整
左孩子：2i
右孩子：2i+1
注：i为节点编号（编号必须是从1开始）
（二）、二叉树的链式存储
设计不同的节点结构可构成不同的链式存储结构
二叉链表节点
有三个域：一个数据域，两个分别指向左右子节点的指针域
三叉链表节点
除二叉链表的三个域外，在增加一个指针域，用来指向节点的父节点
示例
四、二叉树的遍历方法
遍历的定义：
指按某条搜索路线遍访树中的每个节点，使得每个节点均被访问一次且仅被访问一次。
遍历的用途：
它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
二叉树遍历的类型
1、先序遍历（Preorder）
定义：根 → 左子树 → 右子树（DLR）
递归实现 ：
def preorder(node):
if node:
print(node.val) # 访问根
preorder(node.left) # 左子树
preorder(node.right) # 右子树应用场景： 生成前缀表达式 创建二叉树镜像 树结构的序列化
2、中序遍历
定义：左子树 → 根 → 右子树（LDR）
递归实现 python：
def inorder(node):
if node:
inorder(node.left) # 左子树
print(node.val) # 访问根
inorder(node.right) # 右子树应用场景： 二叉搜索树（BST）升序遍历、生成中缀表达式、验证二叉搜索树性质
3、后序遍历
定义：左子树 → 右子树 → 根（LRD）
递归实现：
def postorder(node):
if node:
postorder(node.left) # 左子树
postorder(node.right) # 右子树
print(node.val) # 访问根应用场景： 生成后缀表达式 计算树的高度 / 深度 销毁树结构
4、层序遍历
定义：按层从上到下，每层从左到右
实现：队列（Queue）迭代 应用场景： 检查完全二叉树 广度优先搜索（BFS）
遍历规则
