1. 树的定义
树（Tree）是一种分层数据结构，由节点（Node）和边（Edge）组成，具有以下特点：
- 树中有一个特殊的节点，称为根节点（Root）。
- 除根节点外的每个节点都有且只有一个父节点（Parent），可以有零个或多个子节点（Child）。
- 树中的节点之间有且仅有一条路径相连。
2. 树的术语
- 根节点：树的顶层节点，没有父节点。
- 子节点：一个节点的直接下层节点。
- 父节点：一个节点的直接上层节点。
- 叶子节点：没有子节点的节点。
- 内部节点：至少有一个子节点的节点。
- 路径：从一个节点到另一个节点所经过的节点序列。
- 深度：从根节点到某一节点的路径长度。
- 高度：从某一节点到叶子节点的最长路径长度。
- 层次：节点的深度加1。
3. 树的类型
3.1 二叉树
每个节点最多有两个子节点的树，称为二叉树（Binary Tree）。
- 完全二叉树：除了最后一层，所有层的节点数都达到最大，并且最后一层的节点都在最左边。
- 满二叉树：所有层的节点数都达到最大。
- 平衡二叉树：左右子树的高度差不超过1的二叉树。
3.2 二叉搜索树
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，满足以下性质：
- 每个节点的左子树中的所有节点值都小于该节点值。
- 每个节点的右子树中的所有节点值都大于该节点值。
3.3 平衡树
- AVL树：一种自平衡二叉搜索树，任意节点的两个子树的高度差不超过1。
- 红黑树：一种自平衡二叉搜索树，通过节点着色和旋转操作来保持平衡。
3.4 B树和B+树
- B树：一种自平衡的多路搜索树，广泛应用于数据库和文件系统中。
- B+树：B树的变种，其中叶子节点链表连接，便于范围查询。
4. 树的基本操作
4.1 插入节点
插入节点操作根据树的类型不同而有所不同。例如，在二叉搜索树中，需要根据节点值的大小找到合适的位置插入。
4.2 删除节点
删除节点操作也根据树的类型不同而有所不同。例如，在二叉搜索树中，删除节点时需要考虑三种情况：节点是叶子节点、节点有一个子节点、节点有两个子节点。
4.3 查找节点
查找节点操作根据树的类型不同而有所不同。例如，在二叉搜索树中，可以通过比较节点值来进行查找。
5. 树的遍历
5.1 前序遍历（Pre-order Traversal）
先访问根节点，然后遍历左子树，最后遍历右子树。
def pre_order_traversal(root):if root:print(root.value, end=' ')pre_order_traversal(root.left)pre_order_traversal(root.right)
5.2 中序遍历（In-order Traversal）
先遍历左子树，然后访问根节点，最后遍历右子树。
def in_order_traversal(root):if root:in_order_traversal(root.left)print(root.value, end=' ')in_order_traversal(root.right)
5.3 后序遍历（Post-order Traversal）
先遍历左子树，然后遍历右子树，最后访问根节点。
def post_order_traversal(root):if root:post_order_traversal(root.left)post_order_traversal(root.right)print(root.value, end=' ')
5.4 层次遍历（Level-order Traversal）
按层次从上到下、从左到右遍历节点。
from collections import dequedef level_order_traversal(root):if not root:returnqueue = deque([root])while queue:node = queue.popleft()print(node.value, end=' ')if node.left:queue.append(node.left)if node.right:queue.append(node.right)
6. 树的应用
6.1 表达式树
表达式树是一种用于表示算术表达式的树结构。内部节点是操作符，叶子节点是操作数。通过遍历表达式树，可以进行表达式的求值。
6.2 文件系统
文件系统可以用树结构表示，目录是内部节点，文件是叶子节点。通过遍历文件系统树，可以实现文件的查找、插入和删除操作。
6.3 数据库索引
B树和B+树广泛应用于数据库系统中，用于实现高效的数据检索和范围查询。
7.平衡二叉树与满二叉树比较
| 特性 | 平衡二叉树（Balanced Binary Tree） | 满二叉树（Full Binary Tree） |
|---|---|---|
| 定义 | 任意节点的左右子树高度差不超过1 | 所有节点的度为0或2 |
| 树的高度 | O(log n) | O(log n) |
| 节点个数 | 近似2^h - 1（h为树的高度） | 2^h - 1（h为树的高度） |
| 插入操作 | 需要保持平衡，可能涉及旋转操作 | 插入固定位置，无需旋转 |
| 删除操作 | 需要保持平衡，可能涉及旋转操作 | 删除固定位置，可能涉及重排 |
| 应用场景 | 动态数据的快速查找、插入和删除 | 静态数据的存储和表示 |
| 例子 | AVL树、红黑树 | 满二叉树 |
| 结构特点 | 高度平衡，左、右子树高度差不超过1 | 每层节点数达到最大 |
