数据结构中的二叉树：属性、类型、表示和好处

在不同类型的数据结构中，二叉树比大多数其他类型的用途更多。 它们最显着的应用包括点对点编程、搜索、密码学、带宽比其他网络路由器更高的网络路由器以及 3D 视频游戏。 我们现在将详细讨论数据科学中的二叉树是什么，它们的类型是什么，以及它们是如何表示的。

什么是二叉树？

如果您以前研究过普通树，甚至了解它们的基础知识，您就会知道在这些树中允许不同节点拥有的子节点数量方面没有限制。 在这个意义上，二叉树有点不同。 二叉树中的每个父节点或节点最多只能有两个子节点。

二叉树中的所有节点都具有三个主要组件 -

• 一个数据元素
• 正确的参考
• 左参考

位于树顶部的节点称为根节点。 父节点是那些有子节点的节点。 子节点和父节点通过引用相互连接。 没有任何子节点的节点称为叶节点。

很明显，二叉树中的节点可以有一个孩子、两个孩子或根本没有孩子。 二叉树不是线性数据结构，如队列、数组、堆栈和链表。 相反，它们是分层数据结构。

查看：面向初学者的数据科学项目创意

二叉树节点的重要属性

更好地理解这些属性将帮助您充分利用关于二叉树的讨论。 不同节点的深度定义为将根连接到特定节点的路径上存在的节点数。 这就是为什么根节点的深度为 0。另一方面，二叉树中不同节点的高度是位于连接特定节点和根节点的路径中的节点数。 这就是叶节点高度为0的原因。

如您所见，节点的深度是通过从根节点开始然后向下到达该节点来测量的。 另一方面，在计算高度时，我们从相关节点开始，然后前往根节点。 两次，我们都是从 0 开始。有些人也从 1 开始测量高度和深度，而不是从 0 开始，这没有错，这正是不同的人喜欢的。

现在节点的最大深度定义为二叉树的深度。 类似地，节点的最大高度定义为二叉树的高度。 所以二叉树的高度和深度总是相同的。

了解更多： Python 中的数据结构和算法

什么是二叉搜索树？

二叉搜索树是所有其他类型的二叉树中最常见的。 它是一种专门的二叉树，具有与任何其他形式的二叉树不同且更有用的属性。 究竟什么是二叉搜索树或 BST？ 顾名思义，二叉搜索树用于在树中搜索数据。

BST 具有允许它促进有效搜索的属性。 BST是一棵二叉树，其节点的键分别小于和大于右子树中的节点和左子树中的节点。

二叉树的表示

1. 关联表示

链接表示中的二叉树作为链表存储在内存中。 这些列表的节点不存储在相邻或相邻的内存位置，并且通过与树相关联的父子关系相互链接。

在这个表示中，每个节点都有三个不同的部分——

• 指向右节点的指针，
• 指向左节点的指针，
• 数据元素。

这是更常见的表示。 所有二叉树都包含一个指向根节点方向的根指针。 当您看到一个根节点指向 null 或 0 时，您应该知道您正在处理一个空二叉树。 左右指针存储树的左右子节点的地址。

2. 顺序表示

尽管它比链接表示更简单，但它的低效率使其成为两者中不太受欢迎的二叉树表示。 低效率在于存储不同树元素所需的空间量。 顺序表示使用数组来存储树元素。

二叉树的节点数定义了所使用的数组的大小。 二叉树的根节点位于数组的第一个索引处。 存储特定节点的索引将定义存储节点的左右子节点的索引。 一棵空树的第一个索引为 null 或 0。

二叉树的类型

1. 完全二叉树：完全二叉树是那些节点要么有两个孩子要么没有孩子的二叉树。 换句话说，当除了叶子之外，它的所有其他节点都有两个孩子时，二叉树就变成了完整的二叉树。
2. 完全二叉树：完全二叉树是那些所有不同层次都被完全填充的树。 唯一的例外可能是它们的最后一层，其键主要位于左侧。 二叉堆通常被视为完整二叉树的示例。
3. 完美二叉树：完美二叉树是叶子在同一层，内部节点携带两个孩子的二叉树。 完美二叉树的一个常见例子是祖先家谱。
4. 病态退化二叉树：退化树是那些内部节点有一个孩子的二叉树。 它们的性能水平类似于链表。 了解有关二叉树类型的更多信息。

阅读： R 中最常用的六种数据结构

二叉树的好处

1. 采用分层存储数据的理想方式
2. 反映给定数据集中存在的结构关系
3. 使插入和删除比链表和数组更快
4. 一种灵活的保存和移动数据的方式
5. 用于存储尽可能多的节点
6. 在访问元素时比链表快，比数组慢

结论

在这篇博客中，我们讨论了数据结构中的二叉树是什么，并讨论了它们的类型、表示形式和好处。 树的两个主要用途是搜索和存储数据，因此它们是数据科学及其相关领域研究不可或缺的一部分。

如果您想了解数据结构、数据科学中的二叉树，请查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划是为在职专业人士创建的，并提供 10 多个案例研究和项目、实用的实践研讨会，与行业专家的指导，与行业导师的一对一，与顶级公司的 400 多个小时的学习和工作协助。