二叉树的性质

树是一种常见的非线性数据结构。与数组、栈、队列和链表等线性数据结构不同，树展现出一种分层结构。树的排序信息无关紧要。树由两个指针和节点组成。这两个指针代表父节点的左孩子和右孩子。让我们彻底理解树中使用的术语。

• 树中没有父节点的最高节点被视为树的根。每棵树都有一个根节点。
• 父节点：一个节点的父节点是该节点在节点树中的前一个节点。
• 子节点：一个节点的直接后继节点被称为该节点的子节点。
• 兄弟节点：同一父节点的子节点互为兄弟节点。
• 边：边作为父节点和子节点之间的连接节点。
• 叶子：没有子节点的节点被称为叶子节点。它是树的最后一个节点。一棵树可以有多个叶子节点。
• 一个节点的子树是把该特定节点视为根节点的树。
• 深度：一个节点的深度是它与根节点之间的距离。
• 高度：一个节点的高度是它与子树中最深节点之间的距离。
• 任何节点的最大高度被称为树的高度。这与根节点的高度相同。
• 层：在树中，层是与特定节点对应的父节点的数量。
• 节点度：一个节点的度由它拥有的子节点数量决定。
• 二叉树有 (N+1) 个 NULL 节点，其中 N 是树中节点的总数。

树数据结构的主要用途包括：

• 分层数据操作。
• 使信息可搜索（参见树遍历）。
• 操作数据排序列表。
• 用于创建视觉效果的数字图片。
• 路由协议
• 多阶段决策过程类型（参见商业象棋）。

什么是二叉树？

二叉树是一种由节点组成的数据结构——这些节点也称为左节点和右节点——每个节点最多有两个子节点。树从根节点开始。

二叉树表示

树中的每个节点都包含以下信息：

• 指向左子节点的指针
• 指向右子节点的指针

在 C 语言中，我们可以使用结构体来表示树节点。我们可以利用其他语言的面向对象特性中的类。下面是一个包含整数数据的树节点的示例。

为什么要使用基于树的数据结构？

1. 您可能希望存储自然形成层次结构的信息，这是使用树的原因之一。例如，计算机的文件系统。
   
2. 树提供了合理的访问/搜索速度（通过一些排序，如 BST）（比链表快，比数组慢）。
3. 树提供了有限的插入和删除速度（比数组快，比无序链表慢）。
4. 因为指针用于连接节点，所以树，像链表一样，没有最大节点数。

二叉树的性质

1. 在二叉树中，第 'l' 层最多可以有 2^l 个节点。

注意：在这种情况下，层是指从根到该节点的路径上的节点数量（包括根和该节点）。根的层为 0。

这可以通过归纳法证明。

根 l = 0，2^0 个节点 = 1 (对于根)

假设在“l”层最多有 2^l 个节点。

由于二叉树中的每个节点只能有两个子节点，所以下一层的节点数量将是前一层的两倍，即 2 * 2^l。

2. 高度为“h”的二叉树最多可以有 2^h - 1 个节点。

值得注意的是，在这种情况下，树的高度由从根到叶子的路径上的最大节点数决定。一个只有单个节点的树被认为高度为 1。

这个结果来自于上面的第二点。如果所有层都包含最大数量的节点，那么树就达到了最大节点数。因此，高度为 h 的二叉树最多可以有 1 + 2 + 4 + ... + 2^(h-1) 个节点。这是一个简单的几何级数，有 h 项，其总和为 2^h - 1。

在某些文本中，根的高度被认为是零。在这种情况下，上述公式变为 2^(h+1) - 1。

3. 具有 N 个节点的二叉树的最小高度或最小层数为 Log2(N+1)。

由于每个层必须至少包含一个元素，因此高度不能超过 N。高度为“h”的二叉树可能拥有的最大节点数为 2^h - 1（前面的属性）。因此，节点数不会比这个数量更多或更少。

N <= 2^h - 1

2^h >= N+1

log2(2^h) >= log2(N+1) (两边取对数)

h log2 2 >= log2(N+1) (h 是整数)

h >= | log2(N+1) |

因此，最小可能高度为 | log2(N+1) |

4. 具有 L 个叶子的二叉树至少有 | Log2L | + 1 层。

当所有层完全填满时，二叉树具有最多的叶子（和最少的层）。如果所有叶子都在 L 层，那么下面的公式适用于 L 个叶子。

L <= 2^(l-1) [根据第 1 点] [注意：此处，根节点的层考虑为 1]

l = | Log2L | + 1

其中 l 是最小层数。

5. 在每个节点有 0 个或 2 个子节点的二叉树中，叶子节点的数量总是比有两个子节点的节点多一个。

L = T + 1

其中 L = 叶子节点数

T = 有两个子节点的内部节点数

证明

叶子节点数 (L) 即树底部的总元素数 = 2^(h-1) (h 是树的高度)

内部节点数 = {总节点数} - {叶子节点数} = { 2^h - 1 } - {2^(h-1)} = 2^(h-1) (2-1) - 1 = 2^(h-1) - 1

所以，L = 2^(h-1)

T = 2^(h-1) - 1

因此 L = T + 1

得证

6. 如果 n 是非空二叉树中节点的总数，e 是边的总数，则 e = n-1。

除了根节点，二叉树中的每个节点都只有一个父节点。因此，如果 n 是节点的总数，那么有 n-1 个节点只有一个父节点。每个子节点和其父节点共享同一条边。因此，总共有 n-1 条边。

二叉树应用

• 二叉树以霍夫曼编码树的形式应用于数据压缩方法。
• 表达式树是二叉树的一个应用，在编译器中使用。
• 另一个二叉树应用是优先级队列，它以 O(log N) 的时间复杂度搜索最大值或最小值。
• 显示分层数据。
• 用于电子表格和 Microsoft Excel 编辑应用程序。
• GCC 和 AOCL 等一些知名的计算机编译器使用语法树来执行算术运算。它们有助于数据库中的索引分段和系统中缓存的存储。
• 用于实现优先队列。
• 通过更快地查找项目，用于在计算机中提供快速内存分配（二叉搜索树）。
• 编码和解码操作

二叉树的优点包括

• 二叉树的搜索过程非常快。
• 二叉树可以以简单易懂的方式表示。
• 从父节点到子节点以及反之亦然的操作可以有效地完成。
• 易于理解和应用。
• 金字塔式组织。
• 应反映数据集的结构关系。
• 与数据存储相比，插入数据很简单。
• 内存管理中的数据存储很简单。
• 用户可以快速执行多个节点。
• 可以存储任意数量的数据值。

二叉树的缺点

• 二叉树遍历中的许多指针为空，因此毫无用处。
• 二叉搜索树 (BST) 的访问操作比数组访问操作花费的时间更长。
• 根据树的高度，有一些基本选择。
• 删除节点很困难。
• 树的高度是一个简单的选择。