二叉树与二叉搜索树：二叉树和二叉搜索树之间的区别

介绍

排序是按系统顺序排列数据以便更有效地分析数据的过程。 识别特定记录的过程称为搜索。 如果数据按特定顺序正确排序，则搜索将成为一项简单而有效的任务。 本文处理最重要的非线性数据结构之一，即树。

树主要用于通过展示元素之间的层次关系来表示数据。 例如，目录、家谱。 从技术上讲，一棵树可以定义为一个或多个节点的有限集合“T”，使得一个节点被指定为树的根，而其他节点被划分为 n>=0 不相交的集合 T1、T2、T3， T4…… Tn 和被称为该根节点的子树或子节点。

什么是二叉树？

二叉树是一种非线性数据结构，其中一个节点可以有 0、1 或 2 个节点。 二叉树中的每个节点都称为父节点或子节点。 二叉树的最高节点称为根节点。 每个父节点最多可以有 2 个子节点，即左子节点和右子节点。

二叉树中的节点具有三个字段：

1. 数据元素——它存储节点要存储的数据值。
2. 指向左子节点的指针——它存储对左子节点的引用（或地址）。
3. 指向右子节点的指针——它存储对右子节点的引用。

这样，几个节点组合在一起就构成了一个二叉树。

二叉树可以表示为：

资源

从上图中，根节点 2 有两个子节点（或子节点），7 和 5。7 称为左子节点，5 称为右子节点。 这样，每个子节点都充当其他几个节点的父节点，共同代表二叉树。

查看：二叉树的类型

二叉树中使用的术语

节点：树中终止点的基本表示。

根节点：二叉树的最顶层节点。

父节点：如果一个节点通过边连接到另一个节点，则称为父节点。 在二叉树中，一个父节点最多可以有 2 个子节点。

子节点：如果一个节点有一个前任，它被称为子节点。

叶节点：没有任何子节点的节点称为叶节点。

节点深度：它是从根节点到要测量深度的特定节点的距离。

树的高度：它是从根节点到叶节点的最长距离。

这些是二叉树的一些基本术语。 有了对二叉树的基本了解，让我们继续讨论二叉树的进步，即二叉搜索树。

另请阅读：二分搜索算法：函数、收益、时间和空间复杂性

什么是二叉搜索树

顾名思义，二叉搜索树或 BST 是用于排序、检索和搜索数据的树。 它也是一种非线性数据结构，其中节点按特定顺序排列。 因此，它也被称为“有序二叉树”。 它具有以下属性：

• 节点的左子树的节点仅小于该节点的键。
• 节点的右子树具有仅大于该节点的键的节点。
• 每个节点都有不同的键，并且在二叉搜索树中不允许重复。
• 左右子树也必须是二叉搜索树。

让我们可视化这个概念，以清楚地了解二叉搜索树。

资源

在上图中，我们看到根节点的值为 8。进一步观察，观察到左子树中的所有值都小于根节点的值，并且右子树中的所有值都有大于根节点的值。 此外，值得注意的是，二叉搜索树中的每个值都是唯一的，并且没有重复项。 因此，验证了上述二叉搜索树的性质。

在另一个例子中，我们看到虽然左子树和右子树是二叉搜索树，但在整个树中具有唯一值。 左子树的叶节点的值为 12，大于根节点的值为 12。因此，这不满足 BST 的性质，因此它不是二叉搜索树。

BST 中的搜索操作 –

考虑具有下面给出的值的二叉搜索树。 让我们了解如何执行搜索操作以从二叉搜索树中得到 9。

资源

为了执行二分查找，我们首先将所有整数排列在一个有序数组中。 这称为搜索空间。 该搜索空间应由两个指针组成，称为开始指针和结束指针。 上面给出的二叉搜索树的数组表示为：

第一步是计算数组的中间值，并将其与要搜索的值（在我们的例子中为 9）进行比较。 这是通过计算 n/2 来完成的，其中 n 是数组 (BST) 中的元素总数，为 6。因此，第 3 个元素是中间元素，即 5。

现在中间元素与 9 比较，因为它不等于（更大），所以搜索操作将在右边的数组上执行。 这样，搜索操作就减少了一半，如下图：

下一步，计算中间元素，发现是9，与我们要搜索的元素相匹配。

二叉树与二叉搜索树 -

现在我们对二叉树和二叉搜索树都有基本的了解，让我们快速总结一下它们之间的一些区别。

结论

因此，我们推断，尽管二叉树和二叉搜索树都具有具有节点集合的共同层次结构，但它们在应用上存在一些差异。 二叉树是具有简单规则的基本结构，即没有父节点必须有超过 2 个子节点，而二叉搜索树是二叉树的变体，遵循特定的节点组织顺序。

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

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