什么是树

树是一种层次结构的数据结构，它由节点（也称为顶点）组成，这些节点通过边相互连接。在一个树结构中，任何两个节点之间只能有一条路径。树常常用于表示对象之间的层次关系，如文件系统、组织结构图等。

树的每个节点可以有零个或多个子节点，除了根节点外，每个节点都有一个父节点。根节点是树的起始点，没有父节点。树的一个基本特性是，从任何一个节点出发，沿着边，可以达到它的任何子节点。

树的属性

• 边的数量：树中的边是连接两个节点的线。如果树有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）经常被用于各种不同的应用中，包括搜索引擎索引、数据库索引、内存管理等。

Ternary Search Tree（三元搜索树）是一种特殊的数据结构，它结合了Trie（也称为前缀树）和 Binary Search Tree（二叉搜索树）的特性。在 Trie 中，每个节点通常有 26 个子节点，分别对应 26 个英文字母。而在 Ternary Search Tree中，每个节点只有三个子节点：一个左子节点，一个中子节点，以及一个右子节点。这三个子节点的排列顺序遵循二叉搜索树的规则，即左子节点的值小于当前节点的值，中子节点的值等于当前节点的值，右子节点的值大于当前节点的值。这种数据结构的主要优点是它可以更高效地存储和搜索字符串数据集。由于每个节点有三个指针，而不是26个，所以它可以节省大量空间。此外，由于它结合了二叉搜索树的特性，所以它可以更快地搜索和插入新的键值对。

N叉树（N-ary Tree）

N叉树（N-ary Tree）是一种树形数据结构，它允许每个节点有多达n个子节点，与标准的二叉树不同，后者只允许每个节点最多有2个子节点。下图是一个N-ary Tree的示例：

泛树（Generic Tree）是由节点组成的集合，每个节点是一个数据结构，包含记录和指向其子节点的引用列表（不允许重复引用）。与链表不同，每个节点存储多个节点的地址。每个节点存储其子节点的地址，第一个节点的地址将存储在名为根的单独指针中。泛树是N-ary Tree的一种，具有以下特性：

• 每个节点有多个子节点。
• 每个节点的节点数事先不知道。

根据节点值的不同，树可以分为许多特殊类型。以下是一些常见的类型：

二叉搜索树（Binary Search Tree）：在二叉搜索树中，对于每个节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。这种结构使得查找、插入和删除操作的时间复杂度可以达到O(log n)。然而，如果树不是平衡的，最坏情况下的时间复杂度可能会达到O(n)。

AVL树：AVL树是一种自平衡二叉搜索树。在AVL树中，任何节点的两个子树的高度差都不会超过1。

红黑树（Red-Black Tree）：它是一种自平衡二叉搜索树，其中每个节点都有一个颜色属性，通常为红色或黑色。且满足以下性质：

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是NIL节点）。
• 每个红色节点必须有两个黑色的子节点。
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
• 红黑树的插入和删除操作相对于二叉查找树要复杂，需要进行调整，以满足红黑树的性质。红黑树的应用非常广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。

B树（B-Tree）：它是一种自平衡的搜索树，用于存储关联数组和排序数据。它是一种多叉树，每个节点可以具有多个子节点。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

B+树（B+ Tree）：通常用于数据库和操作系统的文件系统中。它是一种n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。 B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入。在B+树中，所有的叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。所有的非终端节点可以看成是索引部分，节点中仅含其子树（根节点）中的最大（或最小）关键字。

Segment Tree是一种用于解决区间问题的二叉树数据结构，它可以看作是一棵平衡二叉树。每个节点都对应一个区间[l,r]，叶子节点对应的是一个单位区间，即l==r。对于一个非叶子节点[l,r]，它的左儿子所表示的区间为[l,(l+r)/2]，右儿子表示的区间为[(l+r)/2+1,r]。

如果有收获，点个关注支持一下，谢谢！

#文章首发挑战赛#