二叉树常见类型有哪些？

二叉树作为Python中核心的数据结构之一，远不止“每个节点最多两个子节点”这么简单——从无约束的普通二叉树到高度有序的二叉搜索树（BST），再到通过AVL或红黑树实现自平衡以保障性能，从适合数组存储的完全二叉树、严格对称的完美二叉树，到支撑优先队列的堆（最大/最小堆），乃至为访问局部性优化的伸展树和随机化Treap，每种类型都承载着独特的结构规则与工程价值；理解它们的差异与适用场景，不仅能帮你避开O(n)退化的陷阱，更能让你在算法设计、系统实现甚至面试攻坚中游刃有余。

在 Python 中，二叉树是一种常见的数据结构，根据其结构和性质可以分为多种类型。每种类型都有特定的规则和应用场景。以下是几种主要的二叉树类型：

1. 普通二叉树（Binary Tree）

最基础的二叉树形式，每个节点最多有两个子节点：左子节点和右子节点。对节点的值没有特殊限制。

常用于表达层次关系，比如文件系统、表达式树等。

2. 二叉搜索树（Binary Search Tree, BST）

一种有序的二叉树，满足以下条件：

• 左子树的所有节点值小于根节点值
• 右子树的所有节点值大于根节点值
• 左右子树也分别是二叉搜索树

支持高效的查找、插入和删除操作，平均时间复杂度为 O(log n)。

3. 平衡二叉搜索树

为了防止普通二叉搜索树退化为链表（最坏情况 O(n)），引入了自平衡机制。常见实现包括：

• AVL 树：通过旋转操作保持左右子树高度差不超过 1
• 红黑树（Red-Black Tree）：通过颜色标记和旋转维持近似平衡，广泛用于 Python 的字典和集合底层实现（CPython）

4. 完全二叉树（Complete Binary Tree）

除了最后一层外，每一层都被完全填满，且最后一层的节点都靠左排列。

堆（Heap）通常用完全二叉树实现，适合用数组存储，常用于优先队列。

5. 满二叉树（Full Binary Tree）

每个节点要么是叶子，要么有两个子节点，不存在只有一个孩子的节点。

常用于某些编码问题或构造特定结构的场景。

6. 完美二叉树（Perfect Binary Tree）

所有内部节点都有两个孩子，且所有叶子在同一层。

具有最大节点数：深度为 d 的完美二叉树有 2^d - 1 个节点。

7. 堆（Heap）

一种特殊的完全二叉树，分为两种：

• 最大堆（Max Heap）：父节点值 ≥ 子节点值，根是最大值
• 最小堆（Min Heap）：父节点值 ≤ 子节点值，根是最小值

Python 中可用 heapq 模块实现最小堆功能。

8. 伸展树（Splay Tree）与 其他高级变体

虽然不常用作标准库，但在算法题或特定应用中可能出现：

• 伸展树：访问过的节点会“上移”到根，适合局部性访问场景
• Treap：结合二叉搜索树和堆性质的随机化结构

基本上就这些常见类型。在实际编程中，可以根据需求选择合适的二叉树结构，或借助 Python 的内置模块简化实现。

以上就是《二叉树常见类型有哪些？》的详细内容，更多关于的资料请关注golang学习网公众号！