二叉树
二叉堆
二叉查找树
平衡二叉树
- 定义：二叉树是每个节点最多有两个子节点的树结构，子节点通常称为左子节点和右子节点。
- 节点结构：每个节点包含数据元素和指向左右子节点的指针。
- 类型：
- 满二叉树：每层节点都完全填充，叶节点在同一层。
- 完全二叉树：除最后一层外，每层节点都完全填充，最后一层节点尽量靠左。
- 平衡二叉树：左右子树高度差不超过1（如
AVL树、红黑树）。
- 遍历方式：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）、层序（逐层遍历）。
- 应用：搜索、排序、表达式树、堆、哈夫曼编码等。
简单的二叉树实现
- 定义：二叉堆是一种特殊的二叉树，满足堆序性质（父节点值小于或大于子节点值）和完全二叉树性质（除最后一层外全满，最后一层靠左）。
- 类型：
- 最小堆：
父节点值 ≤ 子节点值，根节点为最小值。
- 最大堆：
父节点值 ≥ 子节点值，根节点为最大值。
- 存储：用数组实现，节点
i 的左子节点在 2i+1，右子节点在 2i+2，父节点在 ⌊(i-1)/2⌋。
- 操作：
- 插入：添加元素到末尾，上滤（与父节点比较并交换）。
- 删除（通常删根）：移除根，用末尾元素替换根，下滤（与较小的子节点交换）。
- 构建堆：从最后一个非叶子节点开始下滤。
- 时间复杂度：
- 插入：
O(log n)
- 删除根：
O(log n)
- 构建堆：
O(n)
- 应用：优先队列、堆排序、
Dijkstra算法等。
二叉堆使用演示
简单的二叉堆实现
- 定义：二叉查找树（
BST）是二叉树，每个节点最多有两个子节点，满足：左子树所有节点值 < 当前节点值 < 右子树所有节点值。
- 结构：节点包含值和左右子节点指针，可能是空的（
None）。
- 操作：
- 插入：根据值大小递归插入到左或右子树。
- 查找：从根开始比较，值小去左子树，大去右子树，相等则找到。
- 删除：分三种情况（无子节点、一个子节点、两个子节点），需维护
BST 性质。
- 遍历：中序遍历得到升序序列。
- 时间复杂度（平均）：
- 插入、查找、删除：
O(log n)（平衡时）
- 最坏情况：
O(n)（退化为链表）
简单的二叉查找树实现
- 定义：平衡二叉树是二叉查找树（
BST），其左右子树高度差绝对值不超过1，且左右子树也是平衡的。
- 类型：
- AVL树：最早的平衡二叉树，插入/删除后通过旋转恢复平衡。
- 红黑树：通过节点着色和旋转维持“近似平衡”，广泛用于标准库。
- 性质：
- 高度平衡：保证树高
O(log n)，确保操作效率。
- 查找、插入、删除时间复杂度：
O(log n)。
- 操作：
- 插入：插入后检查平衡因子，必要时通过旋转（左旋、右旋）调整。
- 删除：删除后类似插入，调整平衡。
- 旋转：左旋、右旋、左右旋、右左旋，用于恢复平衡。
简单的平衡二叉树实现