数据结构中树的 4 种类型解释：属性和应用

什么是数据结构中的树？

树是一种表示分层数据的数据结构。 它具有由边连接的节点组成的非线性结构。 在以线性数据结构执行操作的其他类型的数据结构中，复杂性随着数据大小的增加而增加。 然而，树数据结构提供了对非线性数据的更快访问。 各种类型的数据结构和与之相关的算法的可用性，已经成为任务执行的一种简单有效的方式。

与数据结构中的树相关的一些术语是：

• 节点：节点是树数据结构中的一个实体，它包含一个键或一个值以及指向其子节点的指针。
• 子节点：子节点是任何节点的后代。
• 叶节点：没有任何子节点并且是树中最底部的节点的节点。 它们也称为外部节点。
• 根：它是一棵树的最高点。
• 内部节点：至少有一个子节点的节点。
• 边：边是指树中任意两个节点之间的连接。
• 节点的高度：从节点到最深叶子的边数。
• 节点深度：从根到节点的边数。
• 树的高度：根节点的高度。
• 节点度：到该节点的分支总数。
• 森林：不相交的树木的集合。

树的种类

1.二叉树

二叉树是一种树数据结构，其中每个父节点最多有两个子节点。 顾名思义，二进制表示两个，因此，每个节点可以有 0、1 或 2 个节点。 二叉树数据结构如图 1所示。树中的节点 1 包含两个指针，每个指针指向一个子节点。 节点 2 也有两个指针，每个指针指向两个子节点。 而节点 3、5 和 6 是叶节点，因此在左右部分都有空指针。

图 1：二叉树的表示 ( https://www.javatpoint.com/binary-tree )。

二叉树的属性

• I 的每个级别的最大节点数为 2 i 。
• 图 1中树的高度为 3，这意味着最大节点数将为 (1+2+4+8) =15。

• 在高度 h，可能的最大节点数为 (20 + 21 + 22+….2h) = 2h+1 -1。

• 在高度 h 处，可能的最小节点数等于 h+1。

• 最小数量的节点将代表具有最大高度的树，反之亦然。

甚至二叉树也可以分为以下几种树：

• 全二叉树：是一种特殊的二叉树。 在这种树数据结构中，每个父节点或内部节点要么有两个子节点，要么没有子节点。
• 完美二叉树：在这种树数据结构中，每个内部节点正好有两个子节点，所有叶子节点都在同一层级。
• 完全二叉树：它类似于完全二叉树，但有一些区别。
• 每个级别都完全填满。
• 叶节点向树的左侧倾斜。
• 最后一个叶子节点不需要有正确的兄弟节点，即完整的二叉树不必是完整的二叉树。
• 退化或病态树：这些树在父节点的左侧或右侧有一个子节点。
• 偏二叉树：它是一种病态或退化的树，其中树由左节点或右节点支配。 因此，有两种偏斜二叉树，即左偏二叉树或右偏二叉树。
• 平衡二叉树：每个节点的左右子树的高度之差为 0 或 1。

2. 二叉搜索树

这些树结构是非线性的，一个节点连接到多个节点。 该节点最多可以连接两个子节点。 它被称为二叉搜索树，因为：

• 每个节点最多有两个子节点。
• 它可用于在 0(log(n)) 时间内搜索元素，因此称为搜索树。

图：二叉搜索树示例 ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

二叉搜索树的属性是：

• 左子树的所有节点中的值应小于根节点中的值。
• 右子树的所有节点的值都应该大于根节点的值。

3.AVL树

AVL 树是二叉树的类型或变体。 它由来自二叉树和二叉搜索树的属性组成。 由 Adelson Velsky Lindas 发明，这些树是自平衡的，这意味着左子树和右子树的高度是平衡的。 这种平衡是根据平衡因子来衡量的。

平衡系数：

• 它是左子树和右子树之间的差异。
• 平衡因子的值必须是 0、-1 或 1。因此，AVL 树的每个节点都应包含一个平衡因子值，即 0、-1 或 1。
• 平衡因子 =（左子树高度 - 右子树高度）
• 如果每个节点的平衡因子在 -1 到 1 之间，则称 AVL 树为平衡树。

AVL 树中除 -1 到 1 以外的节点的值将表示需要平衡的不平衡树。

• 如果一个节点的平衡因子为 1，则意味着左子树比右子树高一级。
• 如果一个节点的平衡因子为0，则表示左子树和右子树的高度相等。
• 如果一个节点的平衡因子为-1，则表示右子树比左子树高一级或左子树比右子树低一级。

4. B树

B 树是二叉搜索树的一种更通用的形式。 它也被称为高度平衡的 m 路树，其中 m 是树的阶数。 树的每个节点可以有多个键和两个以上的子节点。 在二叉树的情况下，叶节点可能不在同一级别。 但是，在 B 树的情况下，所有叶节点都应该在同一级别。

B树的属性：

• 每个节点 x 的密钥按升序存储。
• 每个节点中都存在一个布尔值“x.leaf”，如果 x 是叶子，则为真。
• 内部节点最多应该有“n-1”个键，其中 n 是树的顺序。 它还应该为每个孩子提供一个指针。
• 除根节点外，所有节点最多有 n 个子节点和至少 n/2 个子节点。
• 树的叶节点具有相同的深度。
• 根节点将至少有 1 个密钥和至少两个子节点。
• 如果 n ≥ 1，那么对于任何高度为 h 且最小度为 t ≥ 2 的 n-key B 树，h ≥ logt (n+1)/2。

应用

• 二叉搜索树可用于在一组元素中搜索一个元素。
• 堆树用于堆排序。
• 现代路由器使用一种称为 Tries 的树来存储路由信息。
• B-Trees 和 T-Trees 主要被流行的数据库用来存储它们的数据。
• 编译器使用语法树来验证每个编写程序的语法。

结论

数据结构提供了一种有组织的方式来存储数据，以便于管理和有效处理。 针对不同类型的数据存在各种类型的数据结构。 根据需要存储的数据类型，由用户选择。

树是这种数据结构的类型，其中可以存储分层类型的数据。 数据存储在节点中，这些节点有时存储称为子节点的其他节点的引用。

根据子节点的数量，树可以分为文章中提到的各种类型。 基于树类型中节点的排列，每个树结构都有相关的属性。 由于不同类别的树可以执行不同类型的操作，这种类型的数据结构已经在排序算法和数据存储中找到了应用。

由 upGrad 和 IIIT-Bangalore 策划的软件开发执行 PG 计划 - 全栈开发专业化，可以帮助您提高个人资料并获得更好的程序员就业机会。