解释了数据结构中的 5 种二叉树

二叉树是一种非线性树数据结构，每个节点最多有 2 个子节点。 二叉树的名称表示数字 2，因此任何二叉树都可以有左孩子和右孩子。

指针将二叉树描绘到最上面的节点，通常称为树的根。 二叉树中的每个节点都包含数据、指向左孩子的指针和指向右孩子的指针。 指针用于实现二叉树。 根指针表示树中的第一个节点。 为了创建二叉树，您需要首先创建一个节点。

在熟悉了数据结构中什么是二叉树之后，你还需要了解二叉树的基本操作。 您可以执行插入元素、删除元素、搜索元素和遍历二叉树等功能。

数据结构中的任何二叉树在计算中都以两种不同的方式使用。 首先，它们用于根据与每个节点链接的特定标签或值访问节点。 其次，它们被用作具有相关分支结构的数据表示。

在了解各种二叉树类型之前，让我们先熟悉一下二叉树中使用的术语。

节点：它在二叉树中保存数据值。

根：任何二叉树中最顶端的节点称为树的根。

大小：它表示二叉树中的节点数。

父节点：二叉树中带有子节点的节点。

子节点：它是源自远离二叉树根的父节点的节点。

内部节点：它是二叉树中至少有一个孩子的节点。

叶节点：它是一个没有孩子的节点。它也可以是一个外部节点。

节点树的深度：它是在特定节点的上下文中计算的。它被称为从特定节点到根的边数。

树的内部路径长度：指二叉树中每个内部节点的层次之和。

一棵树的外部路径长度：它被定义为二叉树中每个外部节点的层次之和。

树中节点的高度：它是从特定节点到二叉树最深叶节点的边数。根的高度将始终大于二叉树中其他节点的高度。

现在让我们检查一下 5种二叉树的详细信息。

二叉树的类型

1. 满二叉树

这种数据结构中的二叉树也被称为 -Proper binary tree 和 Strict binary tree。 它是数据结构中最基本的二叉树类型之一。 完整二叉树被定义为二叉树，其中每个节点应该有两个或根本没有孩子。

它也可以表征为二叉树，其中每个节点都包含除叶节点之外的两个子节点。 存储根节点地址的节点称为根的子节点。 那些没有子节点的节点称为叶节点。

您需要遍历所有节点以检查树是否为二叉树。 如果任一节点有一个子节点，代码将返回“False”。 如果所有节点都有 0 个或 2 个子节点，它将返回“True”。

以下是完整二叉树的属性：

• 叶子节点数等于内部节点数+1。例如，如果内部节点数为4，则叶子节点数等于5。
• 二叉树的最大节点数和节点数相等。 它表示为2h+1 -1。
• 满二叉树的最小节点数是 2h-1。
• 满二叉树的最小高度是 log 2 (n+1) – 1。
• 满二叉树的最大高度为 h = (n+1)/2。

2. 完美二叉树

完美二叉树是其中一种二叉树，其中每个节点必须有 0 或 2 个子节点，并且每个叶节点的级别必须相同。 换句话说，数据结构中的完美二叉树被定义为所有内部节点都拥有两个分支和那些没有分支的节点（叶节点）存在于同一层的树。

在这种情况下，节点的级别是距根节点的距离或高度。 您可以将完美二叉树视为完全二叉树，其中最后一层也被完全占据。

从世界顶尖大学在线学习数据科学课程。 获得执行 PG 课程、高级证书课程或硕士课程，以快速推进您的职业生涯。

3.完全二叉树

完全二叉树是数据结构中的那些类型的二叉树之一，其中树的所有级别都被完全填充。 二叉树的最后一层可能会或可能不会被完全填满。 但是，每个节点都必须位于节点最后一层的最左边。 必须从左侧开始包含节点。

它们是二叉树的基本类型之一，因为它们提供了节点数与树高之间的最佳比率。

以下是完整二叉树的关键属性：

• 最大节点数为 2 h+1 – 1。
• 最小节点数为 2 h 。
• 最小高度为 log 2 (n+1) – 1。

4. 平衡二叉树

在平衡二叉树中，树的高度是节点总数的log 2 。 假设树的高度为 h，树的节点总数为 n。 计算高度的公式是 h = log(n)。 右子树和左子树之间的最大高度差必须为“1”。

差异可以有其他值，如 0 和 -1。 这些类型的二叉树也称为 AVL 树。 平衡二叉树的著名示例之一是红黑树。

您可以实现以下代码来运行平衡二叉树。

私有类节点 {

私有整数值；

私有节点离开；

私有节点权；

}

公共布尔isBalanced（节点n）{

如果（平衡树高度（n）> -1）

返回真；

返回假；

}

public int balancedtreeHeight（节点 n）{

如果（n == null）

返回 0；

int h1 = balancedtreeHeight(n.right);

int h2 = balancedtreeHeight(n.left);

如果（h1 == -1 || h2 == -1）

返回-1；

如果 (Math.abs(h1 – h2) > 1)

返回-1；

如果 (h1 > h2)

返回 h1 + 1；

返回 h2 + 1；

}

检查我们的美国 - 数据科学计划

5. 退化二叉树

退化二叉树是一种不太常用的二叉搜索树类型。 它是一棵二叉树，其中每个节点只有一个孩子，即左孩子或右孩子。 任何节点都不应同时具有左右子节点。

阅读我们的热门美国 - 数据科学文章

结论

如果要将其用于各种应用程序，则必须了解什么是数据结构中的二叉树。 在二叉树上实现不同的功能可以帮助您有效地组织和存储数据。

研究多种类型的二叉树可以帮助您在时间复杂度上更有效地执行操作。 数据科学基础知识，包括二叉树数据结构，可帮助您轻松开启数据科学之旅。 随后，您可以从事高级数据科学项目，以提高您的技能和作品集。

在 upGrad 上开始您的机器学习之旅

如果您想学习数据科学，可以攻读 upGrad 的数据科学理学硕士课程。 这个为期 24 个月的课程传授 Python、部署 ML 模型、使用 Spark 进行 BD 处理、预测分析和统计以及监督和非监督 ML 模型等技能。 该课程适合雄心勃勃的管理人员、MBA 毕业生、工程师和各个领域的专业人士。

完成本课程将帮助您成为数据工程师、大数据分析师、机器学习工程师和数据科学家。