什么是树
树是一种层次结构的数据结构，它由节点（也称为顶点）组成，这些节点通过边相互连接。在一个树结构中，任何两个节点之间只能有一条路径。树常常用于表示对象之间的层次关系，如文件系统、组织结构图等。
树的每个节点可以有零个或多个子节点，除了根节点外，每个节点都有一个父节点。根节点是树的起始点，没有父节点。树的一个基本特性是，从任何一个节点出发，沿着边，可以达到它的任何子节点。
树的属性
- 边的数量：树中的边是连接两个节点的线。如果树有N个节点，那么它将有N-1条边。这个性质是因为在一个树中，除了根节点外，每个节点都有一个父节点，而根节点是唯一没有父节点的节点。因此，总节点数减去1等于边的数量。
- 节点的深度：节点的深度是从根节点到该节点的路径长度。每条边都会增加路径的长度1个单位。因此，节点的深度也可以定义为从树的根节点到该节点的路径中的边数。
- 节点的高度：一个节点的高度可以定义为从该节点到叶子节点的最长路径的长度。在树结构中，叶子节点是没有子节点的节点。
- 树的高度：树的高度是从树的根节点到叶子节点的最长路径的长度。
- 节点的度：附着在该节点上的子树的总数称为节点度。树的最大节点度是树中所有节点中的最大节点度。
二叉树
二叉树每个节点最多有两个子节点，通常称为左子节点和右子节点。左子节点位于节点的左边，右子节点位于节点的右边。二叉树是一种非常常用的数据结构，经常用于各种算法和数据操作中，如二叉搜索树、堆、前缀编码等。
二叉树特性如下：
- 二叉树允许每个节点最多有两个子节点。这是二叉树的基本定义。
- 根节点和叶子节点之间的最大边数决定了二叉树的高度。在二叉树中，叶子节点是没有子节点的节点，而根节点是树的起点。从根节点到叶子节点的最长路径决定了树的高度。
- 二叉树在深度 d 处最多可以有个节点。这是因为每个节点要么是一个叶节点（没有子节点），要么有两个子节点，所以在给定的深度，总的节点数量有一个上限。
- 高度为 h 的二叉树最多可以有 个节点。这是因为对于高度为 h 的二叉树，从根节点到叶子节点的最长路径长度为 h，而除了这条最长路径外的其他路径长度都至少为1，因此总的节点数量有一个上限。
- 在二叉树中，叶子节点数只能比内部节点数多一个。这是因为除了根节点外，每个非叶节点有两个子节点：一个左子节点和一个右子节点。因此，除了根节点外，总节点数减去1等于内部节点数（即非叶子节点数）。所以，叶子节点的数量总是比内部节点的数量多一个。
基于子节点个数的二叉树类型有：
- 满二叉树（Full Binary Tree）
- 退化二叉树（Degenerate Binary Tree）
而基于层完成度的二叉树类型有：
- 完全二叉树（Complete Binary Tree）
- 完美二叉树（Perfect Binary Tree）
- 平衡二叉树（Balanced Binary Tree）
这些不同类型的二叉树具有不同的性质和应用场景。例如，满二叉树和完全二叉树具有良好的空间利用性质，退化二叉树在某些情况下可以表示为链表等。
后续章节会对这些二叉树做详细介绍。
三元树（Ternary Tree）
三元树（Ternary Tree）每个节点最多有三个子节点，通常称为“左”、“中”和“右”。这些子节点可以进一步被解释为其他信息或继续指向其他节点。
三元树（Ternary Tree）相对于其他树形结构有一些优势，例如，查询效率高，结构相对简单。然而，它们也具有一些缺点，例如，如果树变得非常大，可能会变得难以管理。
在三元树（Ternary Tree）中，每个节点都存储一个键（key）和三个子节点的引用。键用于将节点存储在正确的位置，而子节点的引用用于连接到其他节点。
三元树（Ternary Tree）经常被用于各种不同的应用中，包括搜索引擎索引、数据库索引、内存管理等。
