树的分类

根据不同的划分标准，树可以分为多种类型：

1. 按结点有序性

• 有序树：树中结点的各子树从左到右是有顺序的，不能互换。
• 无序树：结点的各子树之间没有顺序关系。

2. 按度数限制

• 一般树：结点的度不受限制（通常 $m$ 叉树即每个结点最多 $m$ 个孩子）。
• 二叉树：每个结点最多两个孩子（$0,1,2$），且区分左、右子树。
• $m$ 叉树：每个结点最多 $m$ 个孩子。

3. 按节点值

• 有序树（如二叉搜索树）：左子树所有结点值小于根，右子树所有结点值大于根。
• 堆：大顶堆（根 ≥ 孩子）、小顶堆（根 ≤ 孩子）。

4. 按形态（特殊二叉树）

• 斜树：所有结点只有左孩子（左斜树）或只有右孩子（右斜树）。
• 满二叉树：所有分支结点都有左、右子树，且所有叶子都在同一层。
• 完全二叉树：除最后一层外，其余层结点数达到最大，最后一层结点向左靠拢。

5. 按平衡性

• 平衡二叉树：任意结点左右子树高度差 ≤ 1（如 AVL 树）。
• 非平衡二叉树：不满足平衡条件。

6. 按实际应用

• 二叉搜索树（BST）：快速查找、插入、删除。
• 堆（Heap）：优先队列的实现。
• 哈夫曼树（Huffman Tree）：最优二叉树，用于编码压缩。
• 红黑树（Red-Black Tree）：近似平衡的二叉搜索树，用于 map、set 等。
• B 树 / B+ 树：多路搜索树，用于数据库和文件系统索引。

总结

分类方式	常见类型
有序性	有序树 / 无序树
度数	二叉树 / $m$ 叉树 / 一般树
形态	斜树 / 满二叉树 / 完全二叉树
平衡	AVL / 红黑树
应用	BST / 堆 / 哈夫曼树 / B 树