树

树（Tree）是一种非线性数据结构，它由节点组成，并且每个节点有零个或多个子节点。树具有以下一些主要特点：

1. 层次结构 ：树的数据组织形式是分层的，根节点位于最顶层，其他节点通过边连接形成分支。
2. 单一父节点 ：除了根节点之外，每个节点都有一个唯一的父节点（即只有一个入口）。
3. 零个或多个子节点 ：节点可以有零个、一个或多个子节点。具有子节点的节点称为父节点，没有子节点的节点称为叶子节点。
4. 递归定义 ：树本身可以被看作是一个递归结构，因为每个子树也是一个树。
5. 路径和层级 ：从根节点到任意节点之间的路径称为路径，路径上的边的数量称为该节点的深度。根节点的深度为0。

常见的树类型包括：

1. 二叉树（Binary Tree） ：

   • 每个节点最多有两个子节点，通常被称为左子节点和右子节点。
   • 二叉搜索树（BST, Binary Search Tree）是一种特殊的二叉树，其中对于每个节点，其左子树的所有节点值小于该节点值，而右子树的所有节点值大于该节点值。

2. 满二叉树（Full Binary Tree） ：

   • 每个非叶子节点都有两个子节点。

3. 完全二叉树（Complete Binary Tree） ：

   • 所有叶子节点都在同一层或仅相差一层，且所有节点都尽可能左对齐。

4. 平衡树（Balanced Tree） ：

   • 例如AVL树和红黑树，这些树在插入和删除操作后通过自平衡调整保持高度的平衡状态。

5. 堆（Heap） ：

   • 堆是一种特殊的完全二叉树，具有特定的性质。最大堆中父节点的值大于或等于其子节点的值，最小堆相反。

6. B树和B+树 ：

   • 用于数据库索引等场景的自平衡搜索树。

7. N叉树（N-ary Tree） ：

   • 每个节点可以有多个子节点，而不仅仅是两个（如二叉树）。