二叉树与二叉搜索树的区别

排序是将数据按逻辑顺序排列的过程，以便能够以最有效的方式进行分析。搜索是在数据库中查找特定记录的操作。如果数据以预定的方式正确组织，则搜索过程将变得简单且节省时间。本文的主题是树，它是非线性数据结构最重要的例子之一。

使用树来表示数据的主要目的是说明被表示结构的各个组件之间的层次关系。例如，目录和家谱。

从更技术的角度来看，树可以定义为一个称为“T”的有限集合，它包含一个或多个节点。在这个集合中，一个节点被指定为树的“根”，其余节点被划分为 $"n\geq{0}"$ 个不相交的集合，称为 $"T_{1},T_{2},T_{3},....T_{n}"$ 这些子树被称为根节点的“子节点”。

什么是二叉树？

这是一种非线性数据结构，其中每个元素最多可以有两个、一个或零个节点。此树中的每个节点都可以充当父节点或子节点。位于树顶部的节点称为根节点。每个父节点最多可以有两个子节点（子节点）。在这种情况下，我们通常分别将其称为左子节点/子节点和右子节点/子节点。

构成二叉树的每个节点都由三个字段组成：

这就是多个节点组合形成二叉树的方式。

以下术语在与二叉树相关的上下文中经常使用：

这些是与二叉树相关的一些基本术语。现在您已经对二叉树有了基本的了解，是时候继续学习二叉树的下一阶段，即二叉搜索树。

二叉搜索树是一种基于节点的、非线性的数据结构类型，它派生自二叉树。它也缩写为 BST。数据检索、分类和分析都可以借助它的帮助来完成。由于它的节点以特定的顺序排列，因此该结构的另一个名称是有序二叉树。

BST 将具有以下特征：

下表重点介绍了二叉树和二叉搜索树之间的主要区别：

比较依据	二叉树	二叉搜索树
定义	二叉树是一种非线性数据结构，其中每个节点最多可以有两个子节点。	BST 是一种二叉树，其节点具有也是二叉搜索树的右子树和左子树。
类型	完全二叉树满二叉树扩展二叉树	AVL 树伸展树 Tango 树 T 树
操作	由于二叉树是无序的，因此插入、删除和查找它们的过程需要花费更多时间。	由于其有序特性，在 BST 中插入、删除和搜索元素的速度比在二叉树中更快。
结构	在二叉树中，节点的排列方式没有顺序。	在 BST 中，左子树包含小于节点元素的元素，而右子树包含大于节点元素的元素。
数据表示	数据表示以分层结构的形式执行。	数据表示以有序格式完成。
重复值	二叉树允许重复值。	二叉搜索树不允许重复值。
速度	由于它是无序的，因此在二叉树中删除、插入和搜索操作的速度比在二叉搜索树中慢。	由于它具有有序属性，因此二叉搜索树执行元素删除、插入和搜索的速度更快。
复杂度	通常，时间复杂度为“O(n)”。	通常，时间复杂度为“O(log n)”。
应用	它用于快速有效地查找数据和获取信息。	它擅长删除元素、插入新元素和搜索项目。
用法	它作为开发各种二叉树结构的基础，例如满二叉树、BST 和完美二叉树等。	它用于实施平衡二叉搜索树，例如 AVL 树、红黑树和其他类似结构。

这两种模型都模拟了一个具有节点集合的层次树结构，每个节点代表一个值；但是，它们在实践方式和使用方式上存在很大差异。

二叉树遵循每个父节点最多只能有两个子节点的规则，而二叉搜索树只是二叉树的一种变体，它遵循相对顺序来确定树中节点的结构方式。

Pradeep Kumar

更新于：2022年7月22日

14K+ 次浏览

完成课程获得认证